Để thăm dò địa chất trước khi khai thác radium trên cao nguyên X, một vệ tinh đặc biệt đã được phóng lên quỹ đạo giúp đo mức độ phóng xạ trên bề mặt.

Cao nguyên được biểu diễn dưới dạng một hình chữ nhật gồm ~m \times n~ ô vuông đơn vị (~m~ hàng, ~n~ cột). Ký hiệu ô vuông ở hàng thứ ~i~ và cột thứ ~j~ là ~(i, j)~.

Kết quả khảo sát cao nguyên đã xác định được mức độ phóng xạ cho từng ô vuông. Mức độ phóng xạ của ô ~(i, j)~ được cho bởi một số nguyên ~a_{ij}~. Độ chính xác của phép đo cao đến mức tất cả các số ~a_{ij}~ đều khác nhau. Ô ~(i, j)~ được coi là phù hợp để khai thác radium nếu giá trị của ~a_{ij}~ lớn nhất ở hàng thứ ~i~ và cũng lớn nhất ở cột thứ ~j~.

Trong quá trình đo, ~q~ lần tinh chỉnh liên tiếp mức độ phóng xạ đã được thực hiện. Cụ thể, lần tinh chỉnh thứ ~k~ đã thay đổi giá trị của ~a_{rc}~ thành một giá trị hoàn toàn lớn hơn. Hơn nữa, sau mỗi lần tinh chỉnh, tất cả các giá trị của ~a_{ij}~ vẫn khác nhau.

Cho các giá trị ban đầu ~a_{ij}~ và danh sách các lần tinh chỉnh, hãy viết chương trình xác định số ô phù hợp để khai thác radium sau mỗi lần tinh chỉnh.

Dữ liệu

• Dòng đầu tiên chứa ba số nguyên dương ~m~, ~n~ và ~q~ (~1 \le m \times n \le 2 \times 10^5~; ~1 \le q \le 2 \times 10^5~) tương ứng là số hàng, số cột của hình chữ nhật và số lần tinh chỉnh.
• Mỗi dòng trong ~m~ dòng tiếp theo chứa ~n~ số nguyên dương, số thứ ~j~ trong dòng thứ ~i~ là giá trị ban đầu của ~a_{ij}~ (~1 \le a_{ij} \le 10^7~, tất cả các ~a_{ij}~ đều khác nhau).
• Tiếp theo có ~q~ dòng mô tả các lần tinh chỉnh, dòng thứ ~k~ chứa ba số nguyên ~r_k~, ~c_k~ và ~x_k~ mô tả sự thay đổi mức độ phóng xạ của ô ~(r_k, c_k)~ thành giá trị mới là ~x_k~ (~1 \le r_k \le m~; ~1 \le c_k \le n~; ~1 \le x_k \le 10^7~). Dữ liệu đảm bảo rằng ~x_k~ hoàn toàn lớn hơn mức độ phóng xạ trước đó trong ô này và tất cả các mức độ phóng xạ đều khác nhau sau mỗi lần thay đổi.

Kết quả

Gồm ~q~ dòng, ở dòng thứ ~k~ chứa một số nguyên là số ô phù hợp để khai thác radium sau lần tinh chỉnh thứ ~k~.

Ví dụ

RADI.INP

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

RADI.OUT

1
2
2

Giải thích:

Trong lần tinh chỉnh thứ nhất, mức độ phóng xạ của ô ~(2, 2)~ được thay từ 5 thành 9. Sau lần tinh chỉnh này, mức độ phóng xạ trong các ô như sau và chỉ có 1 ô phù hợp là ~(2, 2)~.

1 4 3
6 9 2

Trong lần tinh chỉnh thứ hai, mức độ phóng xạ của ô ~(1, 3)~ được thay từ 3 thành 5. Sau lần tinh chỉnh này có 2 ô phù hợp là ~(1, 3)~ và ~(2, 2)~.

1 4 5
6 9 2

Trong lần tinh chỉnh thứ ba, mức độ phóng xạ của ô ~(2, 2)~ được thay từ 9 thành 10. Sau lần tinh chỉnh này có 2 ô phù hợp là ~(1, 3)~ và ~(2, 2)~.

1 4 5
6 10 2

Giới hạn

• Subtask 1 (40% số test): ~1 \le m \times n \le 100~ và ~1 \le q \le 100~;
• Subtask 2 (24% số test): ~1 \le m \times n \le 5000~ và ~1 \le q \le 5000~;
• Subtask 3 (20% số test): ~1 \le m \le 400~, ~1 \le n \le 400~ và ~1 \le q \le 2 \times 10^5~;
• Subtask 4 (16% số test còn lại): không có thêm ràng buộc nào.