Description

The lander of the Mars exploration team will touch down on the Martian surface. Inside the lander, there are multiple obstacle-detecting rovers. After landing, the rovers will leave the lander and move toward the transmitter that arrived earlier.

While moving, the rovers must also collect rock samples. Each rock sample is collected by the first rover that encounters it. Each rock sample can be collected only once. After a rock sample is collected, other rovers may pass through its former location. Rovers cannot pass through obstructed terrain.

In this problem, rovers are limited to moving from the landing position toward the transmitter only in the south or east direction, and multiple rovers may occupy the same position at the same time. If any rover cannot proceed before reaching the transmitter, all rock samples it collected will be lost.

Use a $p \times q$ grid to represent the positions between the lander and the transmitter. The lander is at $(x_1,y_1)$, and the transmitter is at $(x_p,y_q)$.

$$\begin{bmatrix} (x_1,y_1) & (x_2,y_1) & \dots & (x_{p-1},y_1) & (x_p,y_1) \\ (x_1,y_2) & (x_2,y_2) & \dots & (x_{p-1},y_2) & (x_p,y_2) \\ \dots & \dots & \dots & \dots & \dots \\ (x_1,y_{q-1}) & (x_2,y_{q-1}) & \dots & (x_{p-1},y_{q-1}) & (x_p,y_{q-1}) \\ (x_1,y_q) & (x_2,y_q) & \dots & (x_{p-1},y_q) & (x_p,y_q) \end{bmatrix}$$

Given the state of each position, compute the optimal movement plan so that the number of rovers reaching the transmitter is maximized, and the number of rock samples collected by the rovers is also maximized.

Input Format

The first line contains the number of rovers $n$. The next two lines contain $p$ and $q$, respectively.

The next $q$ lines describe the $p \times q$ grid of positions between the lander and the transmitter. Three numbers are used to represent the state of a position: $0$ means flat and unobstructed, $1$ means an obstacle, and $2$ means a rock.

Output Format

Each line contains a rover ID and one movement direction, where $0$ means moving south and $1$ means moving east.

2
10
8
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 1 0 0 0
0 0 0 1 0 2 0 0 0 0
1 1 0 1 2 0 0 0 0 1
0 1 0 0 2 0 1 1 0 0
0 1 0 1 0 0 1 1 0 0
0 1 2 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0

1 1
1 1
1 1
1 1
1 0
1 0
1 1
1 1
1 1
1 1
1 0
1 0
1 1
1 0
1 0
1 0
2 1
2 1
2 1
2 1
2 0
2 0
2 0
2 0
2 1
2 0
2 0
2 1
2 0
2 1
2 1
2 1

Hint

Constraints For $100\%$ of the testdata, $1 \le n, p, q \le 35$.

Translated by ChatGPT 5