Many robots
Assignment
Research robotics group is investigating collective behaviour of interacting groups of robots. The robots are positioned in a rectangular field divided into a grid of 1×1 meter cells. Non-moving robot is always inside some cell, never on a boundary. Each cells contains one non-negative integer. The movement of a robot in the field is divided into successive steps. In one step a robot can move either horizontally or vertically (in one row or in one column of cells) by some number of cells. The system is being tested and the additional movement rule is specified: A robot can move in one step from cell X to cell Y if and only if the distance between the centers of the cells X and Y measured in meters is equal to the sum of integers contained in X and Y.
We say that cell X is reachable for robot A if either A is currently standing in the cell X or A can reach X after some number of steps. During the transfer the robot can choose the direction (horizontal or vertical) of each step arbitrarily.
The initial task for the research group is to cover the field. Covering is a configuration in which for each cell there exists some robot for which this cell is a reachable one. For example, a trivial covering may consist of each cell containing one robot. Such covering is highly inefficient and also the research team might not have enough robots.
Input
The first input line contains two integers M and N separated by space. The values indicate (in this order) the number of rows and columns in the field. Next, there are M lines of input, each represents one row of the field. The line contains N values separated by space and representing the particular cell values in the corresponding field row. The order of input values is the same as the order of values in the field.
Values of M and M do not exceed 500, also, each value in a field does not exceed 500.
Examples
Example 1
4 6
3 1 3 2 0 0
1 3 2 1 2 1
3 3 1 0 1 2
1 2 0 2 3 36Input configuration in Example 1 is depicted in Image 1 above.
Public data
The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.