Pixel Flood Fill

In many graphic software programs, there is a "fill" tool that replaces the color of an entire connected region with a new color. In this problem, we simulate this tool on a pixel grid.

You are given a pixel grid of size \( R \times S \) where each pixel has an initial color. You are also given \( Q \) operations. For each operation, you are given a coordinate \( (r_i, s_i) \) and a new color \( c_i \). When you paint the pixel at \( (r_i, s_i) \), if all pixels in its connected component (defined by 4-directional connectivity) have the same color, then the entire connected component is repainted to \( c_i \).

After processing all \( Q \) operations, output the final state of the pixel grid.

The connectivity is defined in the usual sense: two pixels are connected if they share a common side.

Mathematically, if we denote the grid as \(A\) and an operation \( (r_i, s_i, c_i) \) is performed, let \( oldColor = A[r_i][s_i] \). Then, for every pixel \( (x,y) \) in the same connected component of \( (r_i, s_i) \) (i.e. reachable through 4-directional moves without leaving pixels not equal to \( oldColor \)), update \(A[x][y] = c_i\) (if \( c_i \neq oldColor \)).

inputFormat

The first line contains three integers \( R \), \( S \) and \( Q \) (\(1 \le R, S \le 1000\), \(1 \le Q \le 10^5\)).

Then follow \( R \) lines, each containing \( S \) integers representing the initial color of each pixel in the grid.

Then follow \( Q \) lines, each containing three integers \( r_i \), \( s_i \) and \( c_i \). Here, \( (r_i, s_i) \) denotes the 1-indexed position of the pixel to be painted, and \( c_i \) is the new color.

outputFormat

Output the final grid configuration after processing all \( Q \) operations. The output should consist of \( R \) lines. Each line should contain \( S \) integers, where each integer represents the color of that pixel.

sample

3 3 1
1 1 2
3 1 2
3 3 3
1 1 5

5 5 2
3 5 2
3 3 3