Rectangle Painting Simulation

You are given a rectangle with n rows and m columns. Initially, all cells are uncolored (color 0). Then, k painting operations are performed sequentially. In each operation, you are given a starting cell and a direction. The operation paints the starting cell and all consecutive cells in the specified direction until the boundary of the rectangle is reached. Each operation paints the cells with a unique color equal to the order of the operation (i.e. the first operation paints with color 1, the second with color 2, and so on). Note that if a cell is painted more than once, the later color overwrites the previous one.

The directions are given as follows:

• R: Right (increasing column index)
• L: Left (decreasing column index)
• U: Up (decreasing row index)
• D: Down (increasing row index)

For instance, an operation with starting cell \((x, y)\) and direction defined by the vector \((dx, dy)\) will paint all cells \((x + t \cdot dx,\; y + t \cdot dy)\) for \(t = 0, 1, 2, \dots\) until the next cell is outside the grid.

Your task is to simulate this painting process and print the final color of each cell in the rectangle.

inputFormat

The first line contains three integers \(n\), \(m\) and \(k\) (\(1 \leq n,m \leq 1000\), \(1 \leq k \leq 10^5\)), representing the number of rows, the number of columns, and the number of painting operations respectively.

Each of the following \(k\) lines contains two integers and a character: \(x\), \(y\) and \(d\). Here, \(x\) and \(y\) (1-indexed) denote the starting row and column, and \(d\) is one of 'R', 'L', 'U', 'D', indicating the painting direction.

outputFormat

Output \(n\) lines, each containing \(m\) integers. The \(j\)-th number in the \(i\)-th line represents the final color of the cell in row \(i\) and column \(j\) after all operations. Cells that were never painted should be output as 0.

sample

3 3 2
1 1 R
2 3 U

1 1 2
0 0 2
0 0 0