The working area of the Microsoft Paint program can be represented by a pixel grid with $n$ rows and $m$ columns. Each pixel will have a certain color.
When using the paint bucket tool on a specific pixel, the entire connected region of pixels with the same color with this pixel will be changed to the new color. Pixels are considered adjacent if they share an edge.
Given $q$ painting operations, find the color of the image after performing all $q$ operations.
### Input
- The first line contains two integers $n, m$.
- The next $n$ lines, each containing $m$ integers, represent the initial image.
- The following line contains an integer $q$.
- The next $q$ lines, each containing three integers $x, y, c$, represent a paint operation to color the pixel at row $x$, column $y$ with color $c$.
### Output
- Print $n$ lines, each containing $m$ integers representing the image after all $q$ operations.
### Constraints
- $1 \le n \times m \le 2 \times 10^5$.
- $1 \le q \le 10^5$.
- Colors are within the range $[0, 10^5]$.
### Example
Input:
```
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
```
Output:
```
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
```
### Subtasks
- $8\%$ of the test cases have $1 \le n \times m \le 10^4, 1 \le q \le 10^4$.
- $9\%$ of the test cases have $n = 1, 1 \le m \le 2 \times 10^5, 1 \le q \le 10^5$.
- $31\%$ of the test cases have each pixel containing only two colors $0, 1$.
- The remaining test cases have no additional constraints.
