Bạn đang khám phá một tòa nhà lớn gồm \(R\) hàng và \(C\) cột phòng, tạo thành một lưới ô vuông kích thước \(R \times C\). Ô ở góc trái trên là ô \((1,1)\) và ô ở góc phải dưới là \((R,C)\).
Mỗi căn phòng của tòa nhà này có một mức độ bảo vệ \(A_{i,j}\) và trong mỗi phòng có chứa một gói kẹo loại \(B_{i,j}\). Bạn sẽ bắt đầu tại một căn phòng \((x, y)\) và chỉ được phép đi qua các phòng có mức độ bảo vệ không vượt quá \(k\) thì số loại kẹo khác nhau lớn nhất bạn thu thập được là bao nhiêu.
Lưu ý rằng bạn chỉ có thể di chuyển sang các phòng kề nhau theo bốn hướng: trái, phải, trên, dưới.
Không dừng lại ở đó, tòa nhà này lại thay đổi theo thời gian, nghĩa là sẽ có thời điểm loại kẹo tại một phòng bị thay đổi. Xen giữa những lần thay đổi này, bạn được yêu cầu trả lời các câu hỏi có dạng \((x,y,a)\) như trên.
Bạn cần xử lý \(Q\) truy vấn sau:
- 1 \(x\) \(y\) \(b\) --- loại kẹo tại hàng \(x\), cột \(y\) được thay đổi thành \(b\).
- 2 \(x\) \(y\) \(a\) --- nếu bắt đầu từ phòng \((x, y)\), chỉ được đi qua các phòng có độ khó \(\le a\), hãy tính xem bạn có thể thu thập được bao nhiêu loại kẹo khác nhau trong vùng bạn đi đến.
Ràng buộc: mức độ bảo vệ của các phòng đôi một khác nhau.
\InputFile
- Dòng đầu tiên chứa ba số nguyên \(R\), \(C\), \(Q\) (\(1 \le R \times C \le 10000\))
- \(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 10000\))
-
\(Q\) dòng tiếp theo, mỗi dòng ghi lần lượt một trong hai truy vấn sau:
-
1 \(x\) \(y\) \(b\): \(1 \le x \le R, \; 1 \le y \le C, \; 1 \le b \le 10000;\)
- 2 \(x\) \(y\) \(a\): \(1 \le x \le R, \; 1 \le y \le C, \; 1 \le a \le 10^9;\)
\OutputFile
Với mỗi truy vấn loại 2, in ra một dòng --- số lượng loại phòng khác nhau bạn có thể tiếp cận được.
\Scoring
- Subtask 1 (\(10\%\) số điểm): \(R = 1\), \(1 \le Q \le 1000\), \(A_{1,j} = j\) và không có truy vấn loại 1.
- Subtask 2 (\(20\%\) số điểm): \(1 \le 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\), \(1 \le Q \le 10^5\)
- Subtask 5 (\(26\%\) số điểm): Không giới hạn gì thêm
Example
Test 1
Input
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
Output
4
3
0
Note
Giải thích:
-
Ở truy vấn đầu tiên ta có thể đi đến các ô \((1,1)\), \((1,2)\), \((1,3)\), \((2,3)\), \((3,3)\) và các loại kẹo ta có thể nhận được là \(1,2,3,4\). Nên đáp án là 4.
-
Ở truy vấn cuối cùng, tại ô \((2,2)\) ta đã không thể vượt qua phòng này nên không thu được loại kẹo nào và đáp án là \(0\).
