In a future mission to Mars, a pod containing a number of Mars exploration vehicles (MEVs), will be landing on the surface of Mars. All the MEVs will be released the pod's landing site, from which they will move towards a transmitter that has landed a short distance away. While the vehicles move towards the transmitter, they are required to gather rock samples. A rock may only be sampled once, by the first MEV to visit the rock. After that the rock may not be sampled again, but other MEVs may pass the same position. The vehicles cannot move onto rough terrain. The design of the vehicle is such that it can only move south or east in a path that follows the grid pattern from the pod to the transmitter. More than one MEV may occupy the same position at the same time.

Warning: If a MEV gets stuck, its samples are lost and the sites sampled cannot be resampled.

Task:

Calculate the individual movement of the vehicles to maximise the number of rock samples collected and the number of MEVs that reach the transmitter, using the vehicles that landed with the pod.

Input:

The surface of the planet between the pod and the transmitter is represented by a grid P, Q with the pod position always at position (1,1) and the transmitter located at (P, Q). The definitions of the different types of terrain are as follows:

• Clear terrain: 0
• Rough terrain:1
• Rock sample: 2

 
NumberOfVehicles
P
Q
(X₁Y₁) (X₂Y₁) (X₃Y₁)...(X_P-1Y₁) (X_PY₁ )
(X₁Y₂) (X₂Y₂) (X₃Y₂)...(X_P-1Y₂) (X_PY₂)
(X₁Y₃) (X₂Y₃) (X₃Y₃)...(X_P-1Y₃) (X_PY₃ )
...
(X₁Y_Q-1) (X₂Y_Q-1) (X₃Y_Q-1)...(X_P-1Y_Q-1) (X_PY_Q-1)
(X₁Y_Q) (X₂Y_Q) (X₃Y_Q)...(X_P-1Y_Q) (X_PY_Q)

P and Q are the size of the grid, and NumberOfVehicles is an integer less than 1000, representing the number of vehicles released by the pod. Q lines each represent a row in the surface representation. P and Q will not exceed 255.
 

Sample input:
 

MARS.DAT	Explanation:
2	Number of vehicles
10	Size of P
8	Size of Q
0 0 0 0 0 0 0 0 0 0	Row 1
0 0 0 0 0 1 1 0 0 0	Row 2
0 0 0 1 0 2 0 0 0 0	Row 3
1 1 0 1 2 0 0 0 0 1	Row 4
0 1 0 0 2 0 1 1 0 0	Row 5
0 1 0 1 0 0 1 1 0 0	Row 6
0 1 2 0 0 0 0 1 0 0	Row 7
0 0 0 0 0 0 0 0 0 0	Row 8

 

Output:

A sequence of lines representing the movements of the MEVs towards the transmitter. Each line contains a vehicle number and a digit 0 or 1, where 0 is a move South and 1 a move East.

Sample output:
 

MARS.OUT	Explanation:
1 1	vehicle 1 moves east
1 0	vehicle 1 moves south
2 1	vehicle 2 moves east
2 0	vehicle 2 moves south
1 1	...
1 1
2 0
2 1
2 0
2 0
2 0
2 0
1 1
1 0
1 0
1 0
1 0
1 0
1 0
2 0
2 1
1 1
1 1
1 1
1 1
1 1
2 1
2 1
2 1
2 1
2 1
2 1

 

Scoring:

The calculation of the score will be based on the number of samples collected, as a proportion of the total possible samples, with adjustments made for the arrival or non-arrival of MEVs at the transmitter.

• An illegal move invalidates a solution set. An illegal move occurs when a MEV is moved over rough terrain, or outside the grid.
• Score = (number of samples collected and taken to the transmitter

• A maximum of 100% and a minimum of 0% can be scored.