Controlled Territory Selection

Secret plans of Country A reveal that Country I is divided into an $N\times M$ grid of equal squares, each containing some oil resources. The United Nations only permits Country A to occupy exactly $K$ of these squares. However, to ensure that they can defend their territory effectively, the occupied region must be easy to control: for any two occupied squares, there must exist a path connecting them that uses no more than two directions (selected from left, right, up, and down; different pairs of squares may use different pairs of directions). Your task is to select $K$ squares to occupy. If multiple valid solutions exist, output any one of them.

inputFormat

The first line contains three integers $N$, $M$, and $K$.

Each of the next $N$ lines contains $M$ integers representing the oil resources in the corresponding square.

outputFormat

Output $N$ lines, each containing $M$ numbers. Print 1 if the square is occupied and 0 otherwise. The output must contain exactly $K$ ones, and the occupied squares must satisfy the connectivity condition described in the problem statement.

sample

3 4 5
1 2 3 4
5 6 7 8
9 10 11 12

1 1 1 1
1 0 0 0
0 0 0 0