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

Giả sử bản đồ mô tả cao nguyên như một hình chữ nhật bao gồm ~n \times m~ ô vuông đơn vị. Ký hiệu ô vuông thứ ~j~ trong hàng ~i~ là ~(i, j)~.

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

Trong quá trình quan sát, có ~q~ lần điều chỉnh liên tiếp mức độ phóng xạ. Cụ thể, lần điều chỉnh thứ ~k~ thay đổi giá trị của ~a_{r_k, c_k}~ thành một giá trị lớn hơn. Sau mỗi lần điều chỉnh, tất cả các giá trị ~a_{i,j}~ vẫn khác nhau.

Xác định số lượng ô vuông đơn vị phù hợp để khai thác radium sau mỗi lần điều chỉnh thông tin.

Input

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

Output

• Đầu ra chứa ~q~ dòng, dòng thứ ~k~ trong số các dòng này phải in ra một số là số lượng ô vuông đơn vị phù hợp để khai thác radium sau lần cập nhật thông tin thứ ~k~.