在看到小智成功成为最强宝可梦大师后，熊猫先生也想追随他的脚步，成为最强！为此，他希望收集尽可能多不同类型的宝可梦来填满他的宝可梦图鉴，并成为最强。然而，在他的道路上有许多其他宝可梦训练家，他必须击败他们才能实现他的目标。

熊猫先生和宝可梦们生活在一个可以用 $R \times C$ 的网格表示的世界中，该网格有 $R$ 行和 $C$ 列。熊猫先生只能在相邻的方格之间移动。左上角的方格标记为 $(1, 1)$，右下角的方格标记为 $(C, R)$。每个网格方格中都有一位宝可梦训练家，熊猫先生必须与他/她战斗才能通过该方格并获得该训练家拥有的宝可梦。每位宝可梦训练家相对于其他训练家都有自己的等级，这决定了谁是更强的训练家。我们假设所有宝可梦训练家的等级都不同（以确保每场战斗都有明确的胜者）。在方格 $(j, i)$ 的宝可梦训练家等级为 $L_{ij}$，且他/她在战斗中使用类型为 $P_{ij}$ 的宝可梦。

为了让事情变得更加困难，世界在不断变化，因此宝可梦训练家有时会改变他们用于战斗的宝可梦类型，以增加获胜的机会。正因为如此，熊猫先生想要规划什么时候是开始他的冒险的最佳时机。在某些时间点，他想知道如果他从方格 $(X_q, Y_q)$ 出发，并且只能击败等级至多为 $L_q$ 的宝可梦训练家，他将能够获得多少种不同类型的宝可梦。请记住，如果他无法击败某个方格的宝可梦训练家，他就无法通过该方格。多次击败拥有相同宝可梦类型的不同训练家，该宝可梦类型只会被计算一次。

输入格式

您的程序必须从标准输入中读取。

输入的第一行包含三个正整数 $R$，$C$ 和 $Q$。保证 $R \times C \le 50000$。

接下来是 $2R + Q$ 行。

• 前 $R$ 行输入每行将包含 $C$ 个整数。第 $i$ 行的第 $j$ 个整数表示 $L_{ij}$。保证 $1 \le L_{ij} \le 10^9$ 且所有值互不相同。
• 接下来的 $R$ 行输入每行将包含 $C$ 个整数。第 $i$ 行的第 $j$ 个整数表示 $P_{ij}$。保证 $1 \le P_{ij} \le 50000$。

• 最后 $Q$ 行每行包含 4 个整数，表示一个查询。

  • 如果该行的第一个整数是 1，则表示第 1 类查询，接下来的 3 个整数表示 $X_q, Y_q, P_q$。这意味着位于 $(X_q, Y_q)$ 的训练家改为使用类型为 $P_q$ 的宝可梦。保证 $1 \le P_q \le 50000$。
  • 如果该行的第一个整数是 2，则表示第 2 类查询，接下来的 3 个整数表示 $X_q, Y_q, L_q$。这意味着熊猫先生想知道，如果他从方格 $(X_q, Y_q)$ 出发，且只能击败等级至多为 $L_q$ 的宝可梦训练家，他将能够获得多少种不同类型的宝可梦。保证 $1 \le L_q \le 10^9$。

输出格式

您的程序必须仅输出到标准输出。

对于每个第 2 类查询，输出一行，包含一个整数，即熊猫先生能够获得的不同宝可梦类型的数量。

子任务

每个测试点的最大运行时间限制为 5.0 秒。您的程序将在满足以下限制的输入实例上进行测试：

样例

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

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

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

输出样例 3

1
2
0
2

输入样例 4

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

输出样例 4

2
4
0
3

说明

样例 4 解释

对于第一个第 2 类查询，熊猫先生只能通过击败等级为 1, 2, 3 和 4 的宝可梦训练家来获得类型为 3 和 6 的宝可梦。

对于第二个第 2 类查询，熊猫先生可以获得所有类型的宝可梦，因为他可以击败除等级为 11 的训练家之外的所有宝可梦训练家。

对于第三个第 2 类查询，熊猫先生无法击败起点处的训练家，因此他无法移动到任何地方，从而无法获得任何宝可梦。

对于第四个第 2 类查询，熊猫先生可以获得 3 种类型的宝可梦，因为位于 $(2, 2)$ 的训练家现在使用的是类型为 7 的宝可梦。