Spirals

Time limit1sMemory limit64 MB

Summary

K spirals walk outward with run lengths 1,1,2,2,... on an N by M grid; for each cell print the earliest step any spiral reached it, within a 10^100 step limit.

Level: Medium6 of 10
Topics: Implementation, Simulation, Math, Array
Solved: No attempts yet

Problem

There is a table with $N$ rows and $M$ columns. The table starts empty, and $K$ spirals are placed on it. Each spiral starts moving from its own starting cell, turning either clockwise or counter-clockwise.

One spiral moves by the following rules.

In step 1 the spiral is on its starting cell.
After that it walks straight runs one after another. The run lengths are $1, 1, 2, 2, 3, 3, 4, 4, \dots$ in that order, and a run of length $L$ is $L$ single-cell moves in the same direction.
The first run goes up, that is, toward smaller row numbers.
The direction turns once at the end of every run. A clockwise spiral repeats up, right, down, left. A counter-clockwise spiral repeats up, left, down, right.

All spirals move at the same time, and each of them advances one cell per step. A spiral sometimes leaves the table and comes back inside it later.

After exactly $10^{100}$ steps, the value of each cell is the number of the earliest step in which some spiral stood on that cell.

Image 1: a spiral moving counter-clockwise

Image 2: a spiral moving clockwise

Input

The first line contains $N$ , $M$ ( $1 \le N, M \le 50$ ) and $K$ ( $1 \le K \le N \times M$ ).

Each of the next $K$ lines contains integers $X_i$ , $Y_i$ and $T_i$ ( $1 \le X_i \le N$ , $1 \le Y_i \le M$ , $0 \le T_i \le 1$ ). $X_i$ and $Y_i$ are the row and the column of the starting cell of the $i$ -th spiral. $T_i = 0$ means clockwise and $T_i = 1$ means counter-clockwise. No two spirals share a starting cell.

Output

Print $N$ lines with $M$ numbers each, separated by single spaces. The $j$ -th number on the $i$ -th line is the value of the cell in row $i$ and column $j$ .

Note

The third example is explained by the picture below.

Third example

To make the picture easier to read, the letter A is attached to the numbers left by the first spiral and the letter B to the numbers left by the second spiral. Only the first 20 steps of the first spiral and the first 21 steps of the second spiral are drawn. The gray cells are the cells of the table. The other cells lie outside the table and are drawn to show how the spirals move outside it.

Examples3

Example 1
Input
```
3 3 1
2 2 0
```
Expected output
```
9 2 3
8 1 4
7 6 5
```
Example 2
Input
```
3 3 1
2 2 1
```
Expected output
```
3 2 9
4 1 8
5 6 7
```
Example 3
Input
```
3 3 2
1 1 0
1 2 0
```
Expected output
```
1 1 4
6 5 5
19 18 17
```