我们将画图软件（MS Paint）的绘图区域表示为一个由单位正方形组成的矩形网格，分为 $R$ 行和 $S$ 列。网格中的每个正方形代表一个像素，可以用 $10^5$ 种不同的颜色之一进行着色。当用户在颜色为 $B$ 的像素 $(r, s)$ 上使用颜色为 $A$ 的“油漆桶”工具时，该像素 $(r, s)$ 的同色邻域中的所有像素都会将颜色更改为 $A$。像素 $(r, s)$ 的同色邻域是指从 $(r, s)$ 出发，在四个基本方向（上、下、左、右）上移动，且沿途不改变像素颜色所能到达的像素集合。请注意，像素 $(r, s)$ 本身也是其同色邻域的一部分。

给你一幅在画图软件中绘制的初始图像，以及 $Q$ 个需要按给定顺序执行的指令。每个指令会告诉你应该在哪个像素上使用油漆桶工具以及使用什么颜色。你的任务是求出在执行完所有指令后，图像的最终状态。

输入格式

第一行包含两个整数 $R$ 和 $S$，含义如题面所述。

接下来的 $R$ 行，每行包含 $S$ 个小于 $100\,000$ 的非负整数，表示画图软件中的初始图像。更具体地，图像第 $i$ 行的第 $j$ 个数字表示像素 $(i, j)$ 的颜色。

下一行包含一个整数 $Q$，含义如题面所述。

接下来的 $Q$ 行中，第 $i$ 行包含三个整数 $r_i$、$s_i$ 和 $c_i$（$1 \le r_i \le R$，$1 \le s_i \le S$，$0 \le c_i < 100\,000$），表示第 $i$ 个指令，即在像素 $(r_i, s_i)$ 上使用颜色为 $c_i$ 的油漆桶工具。

输出格式

你应该以与输入相同的格式输出图像的最终状态。

子任务

样例

输入样例 1

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 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

输入样例 2

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

输出样例 2

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

输入样例 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

输出样例 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

说明

样例 1 说明：题面中的插图对应样例 1 的输入。白色对应数字 $0$，红色对应数字 $1$，蓝色对应数字 $2$，绿色对应数字 $3$，黄色对应数字 $4$。