Reconstructing Spirals

Little Stjepan had a vivid image in his mind after a night at the nightclub in Zagreb – an image of number spirals drawn on a table. The table has N rows and M columns, and there are K spirals. For each spiral, you are given its starting position and its moving direction: either clockwise or counter‐clockwise. The spirals move one step at a time in the following manner:

1. Initially, the table is empty and each spiral marks its starting cell at step 0.
2. At every subsequent step, each spiral moves to its next cell along a spiral path. It is possible for a spiral to leave the boundaries of the table and later return.
3. After exactly $10^{100}$ steps, every cell in the table contains the step number at which it was touched for the first time by any spiral. If a cell is never touched by any spiral, the cell remains 0.

The spiral paths are defined as follows:

Clockwise spiral: Starting from its initial position, the spiral moves in a cyclic order: right, down, left, up. In its first phase it moves 1 step right, then 1 step down, then 2 steps left, then 2 steps up, then 3 steps right, 3 steps down, and so on.

Counter‐clockwise spiral: Starting from its initial position, the spiral moves in the cyclic order: left, down, right, up. In its first phase it moves 1 step left, then 1 step down, then 2 steps right, then 2 steps up, then 3 steps left, 3 steps down, and so on.

Your task is to reconstruct the final table. For every cell, output the earliest step number at which any spiral touched that cell, or 0 if it was never touched.

inputFormat

The first line contains three integers N, M, and K — the number of rows, columns, and spirals respectively.

Then follow K lines. Each of these lines contains three integers r, c, and d: the starting row, starting column (1-indexed), and the direction of the spiral. Here, if d is 0 the spiral is clockwise, and if d is 1 the spiral is counter‐clockwise. Note that the starting position may lie outside the table.

outputFormat

Output N lines, each containing M space‐separated integers. The j-th integer in the i-th line is the earliest step at which cell (i, j) was touched, or 0 if never touched.

sample

3 3 1
2 2 0

6 7 8
5 0 1
4 3 2