Spirals

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

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.

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$.

The third example is explained by the picture below.

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.