题目描述

你一定使用过画图软件中的"一键填充"功能吧？如果从像素层面来理解，当一个大连通块内所有像素颜色相同时，对其中任何一个像素进行染色，整个连通块内的所有像素都会被染成相同的颜色。

现在给定一个 $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

假设颜色对应关系为：

0：白色

1：红色

2：蓝色

3：绿色

4：黄色

那么染色效果如下图所示

数据规模与约定

$1 \le R, S \le 2000$

$1 \le Q \le 10^5$

$1 \le r_i \le R$

$1 \le s_i \le S$

$0 \le c_i \le 10^5$