Description

We will represent the drawing area of MS Paint as a rectangular grid of unit squares divided into $R$ rows and $S$ columns. Each square of the grid represents a single pixel that can be colored in one of the $10^5$ different colors. When the user applies the so called bucket tool with color $A$ on a pixel $(r, s)$ which is colored in the color $B$, then all pixels in the monochrome neighborhood of pixel $(r, s)$ change their color to $A$. Monochrome neighborhood of a pixel $(r, s)$ is a set of pixels that are reachable by walking from $(r, s)$ in the four general directions (up, down, left and right) without changing the color of the pixel along the way. Note that the pixel $(r, s)$ is itself a part of its monochrome neighborhood.

You are given a starting image drawn in MS Paint along with $Q$ instructions that should be executed in the given order. Each instruction tells you on which pixel should you apply the bucket tool and with what color. Your task is to how the image looks like after all instructions are executed.

Input

The first line contains integers $R$ and $S$ from the task description.
Each of the next $R$ lines contains $S$ non-negative integers less than $100\ 000$ that represent the starting image drawn in MS Paint. More precisely, the $j$-th number in the $i$-th row of the image represents the color of the pixel $(i, j)$.
The next line contains an integer $Q$ from the task description.
The $i$-th of the next $Q$ lines contains integers $r_i$, $s_i$ and $c_i$ ($1 ≤ r_i ≤ R$, $1 ≤ s_i ≤ S$, $0 ≤ c_i < 100\ 000$), which represent the $i$-th instruction that tells you to use the bucket tool with color $c_i$ on the pixel $(r_i, s_i)$.

Output

You should output the final state of the image in the same format as it was given in the input.

12 11
1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 0 0 0 1 1 1 1
1 1 1 0 0 0 0 0 1 1 1
1 1 0 0 0 0 0 0 0 1 1
1 0 0 0 2 2 2 0 0 0 1
1 0 0 0 2 2 2 0 0 0 1
1 0 0 0 2 2 2 0 0 0 1
1 0 0 0 0 0 0 0 0 0 1
1 1 0 0 0 2 0 0 0 1 1
0 1 1 0 0 2 0 0 1 1 0
0 0 1 1 0 0 0 1 1 0 0
0 0 0 1 1 1 1 1 0 0 0
2
5 5 3
6 2 4

1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 4 4 4 1 1 1 1
1 1 1 4 4 4 4 4 1 1 1
1 1 4 4 4 4 4 4 4 1 1
1 4 4 4 3 3 3 4 4 4 1
1 4 4 4 3 3 3 4 4 4 1
1 4 4 4 3 3 3 4 4 4 1
1 4 4 4 4 4 4 4 4 4 1
1 1 4 4 4 2 4 4 4 1 1
0 1 1 4 4 2 4 4 1 1 0
0 0 1 1 4 4 4 1 1 0 0
0 0 0 1 1 1 1 1 0 0 0

4 4
1 0 1 3
1 3 2 2
3 3 1 2
2 2 1 3
3
1 2 3
3 2 1
4 2 3

1 1 1 3
1 1 2 2
1 1 1 2
3 3 1 3

6 6
1 2 1 2 2 2
3 1 2 1 3 1
3 3 2 3 2 2
2 3 1 3 3 2
3 3 3 3 3 3
2 3 2 2 2 1
4
6 2 2
3 5 2
3 2 3
1 2 3

1 3 1 2 2 2
3 1 3 1 3 1
3 3 3 3 3 3
3 3 1 3 3 3
3 3 3 3 3 3
3 3 3 3 3 1

Scoring