题目描述

雨雪国的地图可以抽象成一张 $R \times C$ 的网格，左上角 $(1, 1)$，右下角 $(C, R)$。每个格子都涂有一个颜色，位于 $(j, i)$ 的格子颜色为 $C_{i,j}$，海拔为 $L_{i,j}$。

顾名思义，雨雪国是个多雨多雪的国度。当雨雪降落在格子 $(x, y)$ 时，就会向四联通的格子们蔓延，只会蔓延到海拔不超过 $L$ 的格子。所有这些格子上涂有的颜色被混在一起，小 G 想知道其中有多少种不同的颜色。注意：如果 $(x, y)$ 的海拔超过了 $L$，任何格子都淋不到雨。

为了增加趣味性，小 G 有时还会修改某个格子上的颜色。所有下雨的日子（也就是询问）互不影响。

输入格式

第一行，三个正整数 $R, C, Q$。

接下来 $R$ 行，每行 $C$ 个正整数，其中第 $i$ 行第 $j$ 个数表示 $L_{i,j}$。

接下来 $R$ 行，每行 $C$ 个正整数，其中第 $i$ 行第 $j$ 个数表示 $C_{i,j}$。

接下来 $Q$ 行，每行 $4$ 个整数：

• 如果第一个数是 $1$，则接下来三个数依次为 $x, y, c$，表示将 $(x, y)$ 的颜色改成 $c$。
• 如果第一个数是 $2$，则接下来三个数依次为 $x, y, L$，表示一个下雨的日子，也即询问。

输出格式

对每个询问，输出一行表示答案。

样例

样例 1

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

1
2
0
1

样例 2

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

2
4
0
3

样例 3

3 3 5
1 4 3
11 2 7
5 10 6
1 1 1
2 1 2
1 2 1
2 2 1 6
2 2 3 10
2 3 2 3
1 2 2 2
2 2 1 4

1
2
0
2

数据范围

• 子任务 $1$，分值 $11$ 分，保证 $R = 1, Q \le 10^3$，位置 $(X, 1)$ 的海拔为 $X$。
• 子任务 $2$，分值 $16$ 分，保证 $Q \le 10$。
• 子任务 $3$，分值 $20$ 分，保证 $1 \le C_{i,j} , c \le 2$。
• 子任务 $4$，分值 $24$ 分，保证 $R = 1$，位置 $(X, 1)$ 的海拔为 $X$。
• 子任务 $5$，分值 $29$ 分，无特殊限制。

对所有数据，$1\le R\times C\le 5\times 10^4$，$1\le Q\le 10^5$，$1\le C_{i,j},c\le 5\times 10^4$，$1\le L_{i,j}\le 10^9$，保证所有格子海拔互不相同。