题目描述

你一定用过画图软件的一键填充功能吧？如果拓展到像素层面中，如果一个大连通块内所有像素的颜色相同，那么将一个像素染色，那么整个连通块内的所有像素都会被染色。

现在给定一个 $R\times S$ 的像素图，给定 $Q$ 个染色操作：

• 将 $(r_i,s_i)$ 染为颜色 $c_i$。

求染色过后的整个像素图。

输入格式

第一行两个整数 $R,S$ 代表像素图大小。
接下来 $R$ 行每行 $S$ 个整数，代表像素图的初始颜色。
第 $R+2$ 行一个整数 $Q$ 代表操作个数。
接下来 $Q$ 行每行三个整数 $r_i,s_i,c_i$ 代表一次染色操作。

输出格式

$R$ 行每行 $S$ 个整数代表染色后的像素图。

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

提示

样例 1 解释

假设 $0$ 为白色，$1$ 为红色，$2$ 为蓝色，$3$ 为绿色，$4$ 为黄色，那么如下图所示：

数据规模与约定

本题采用捆绑测试。

• Subtask 1（8 pts）：$1 \le R \times S \le 10^4$，$1 \le Q \le 10^4$。
• Subtask 2（9 pts）：$R=1$，$1 \le S \le 2 \times 10^5$，$1 \le Q \le 10^5$。
• Subtask 3（31 pts）：$1 \le R \times S \le 2 \times 10^5$，$1 \le Q \le 10^5$，颜色只有 $0$ 和 $1$。
• Subtask 4（52 pts）：$1 \le R \times S \le 2 \times 10^5$，$1 \le Q \le 10^5$。

对于 $100\%$ 的数据，$1 \le r_i \le R$，$1 \le s_i \le S$，$0 \le c_i \le 10^5$，颜色区间为 $[0,10^5]$。

说明

翻译自 Croatian Olympiad in Informatics 2020 A Paint。