Cho bảng chữ nhật ~m~ x ~n~ (các hàng được đánh số từ ~1~ tới ~m~ từ trên xuống dưới, các cột được đánh số từ ~1~ tới ~n~ từ trái sang phải). Mỗi ô ở hàng ~i~ cột ~j~ có chứa một số nguyên ~a_{ij}~.

Tổng hàng cột của một toạ độ ~[i,j]~ được tính bằng tổng của tất cả những số nằm trên hàng ~i~ và cột ~j~.

Ví dụ, với bảng ~4~ x ~6~, tổng hàng cột của toạ độ ~[3, 4]~ là tổng của những ô sau:

Cho ~q~ truy vấn gồm 2 loại như sau:

• ~1~ ~x~ ~y~ ~d~: Tăng ~a_{xy}~ lên ~d~ (~d~ là số nguyên không âm).
• ~2~: Đưa ra tổng hàng cột lớn nhất trong bảng.

Yêu cầu

Cho bảng số ~m~ x ~n~ và ~q~ truy vấn. Với mỗi truy vấn loại ~2~, in ra tổng hàng cột lớn nhất tại thời điểm truy vấn.

Input

• Dòng đầu tiên chứa 3 số nguyên dương ~m~, ~n~, ~q~ ~(1≤m,n,q≤2000)~ cách nhau một dấu cách.
• ~m~ dòng sau, mỗi dòng chứa ~n~ số nguyên ~a_{ij}~ có giá trị tuyệt đối không vượt quá ~10^9~ cách nhau một dấu cách.
• ~q~ dòng tiếp theo, mỗi dòng là một truy vấn có dạng ~1~ hoặc ~2~.

Output

Gồm nhiều dòng, mỗi dòng tương ứng với kết quả của các truy vấn dạng ~2~.

Sample Input

3 4 5
0 0 0 0
0 0 1 0
1 1 0 1
2
1 2 1 2
2
1 1 3 2
2

Sample Output

4
5
6

Giải thích

Subtask

• Có 50% số test ứng với 50% số điểm có ~1≤m,n,q≤200~;
• 50% số test còn lại tương ứng với 50% số điểm không có giới hạn gì thêm.