Thu thập kẹo

Một tòa nhà gồm \(R\) hàng và \(C\) cột phòng, tạo thành lưới \(R \times C\). Phòng ở hàng \(i\), cột \(j\) được ký hiệu là \((i, j)\); phòng góc trái trên là \((1, 1)\), phòng góc phải dưới là \((R, C)\).

Phòng \((i, j)\) có mức độ bảo vệ \(A_{i,j}\) và chứa một gói kẹo thuộc loại \(B_{i,j}\). Từ một phòng, bạn chỉ có thể sang các phòng chung cạnh (trên, dưới, trái, phải).

Nếu xuất phát tại phòng \((x, y)\) và chỉ được phép đi vào các phòng có mức độ bảo vệ không vượt quá \(a\) (kể cả phòng xuất phát), bạn sẽ thu được kẹo ở mọi phòng đến được. Nếu bản thân phòng \((x, y)\) có \(A_{x,y} > a\) thì bạn không vào được phòng nào và không thu được kẹo.

Mức độ bảo vệ của các phòng không đổi, nhưng loại kẹo trong các phòng có thể bị thay đổi theo thời gian. Bạn cần xử lý lần lượt \(Q\) truy vấn thuộc một trong hai dạng:

• 1 x y b — loại kẹo trong phòng \((x, y)\) được đổi thành \(b\);
• 2 x y a — xuất phát từ phòng \((x, y)\), chỉ đi qua các phòng có mức độ bảo vệ \(\le a\), hỏi thu được bao nhiêu loại kẹo khác nhau.

Input

• Dòng đầu tiên chứa ba số nguyên \(R\), \(C\), \(Q\) \((1 \le R \times C \le 10^4,\ 1 \le Q \le 10^5)\).
• \(R\) dòng tiếp theo, mỗi dòng gồm \(C\) số nguyên \(A_{i,j}\) \((1 \le A_{i,j} \le 10^9)\).
• \(R\) dòng tiếp theo, mỗi dòng gồm \(C\) số nguyên \(B_{i,j}\) \((1 \le B_{i,j} \le 10^4)\).
• \(Q\) dòng cuối, mỗi dòng là một truy vấn:
• 1 x y b với \(1 \le x \le R,\ 1 \le y \le C,\ 1 \le b \le 10^4\);
• 2 x y a với \(1 \le x \le R,\ 1 \le y \le C,\ 1 \le a \le 10^9\).

Output

Với mỗi truy vấn loại \(2\), in ra trên một dòng số loại kẹo khác nhau thu được.

Subtask

• Subtask 1 (\(10\%\) số điểm): \(R = 1\), \(Q \le 1000\), \(A_{1,j} = j\) và không có truy vấn loại \(1\).
• Subtask 2 (\(20\%\) số điểm): \(Q \le 100\).
• Subtask 3 (\(24\%\) số điểm): không có truy vấn loại \(1\).
• Subtask 4 (\(20\%\) số điểm): \(R = 1\).
• Subtask 5 (\(26\%\) số điểm): không có ràng buộc gì thêm.

Sample Input 1

3 3 4
6 2 1
8 7 4
3 9 5
1 2 1
1 2 3
1 3 4
2 2 3 6
1 1 2 1
2 2 3 6
2 2 2 4

Sample Output 1

4
3
0

Notes

• Truy vấn thứ nhất: từ phòng \((2, 3)\) với \(a = 6\) có thể đến các phòng \((1,1)\), \((1,2)\), \((1,3)\), \((2,3)\), \((3,3)\), chứa các loại kẹo \(1, 2, 1, 3, 4\) — có \(4\) loại khác nhau.
• Truy vấn thứ hai đổi loại kẹo ở phòng \((1, 2)\) thành \(1\), nên truy vấn thứ ba chỉ còn các loại \(1, 3, 4\).
• Truy vấn cuối: phòng \((2, 2)\) có mức độ bảo vệ \(7 > 4\) nên không vào được, đáp án là \(0\).