Nguồn: Free Contest

Có một bảng số gồm ~N~ dòng và ~M~ cột. Các dòng được đánh số từ ~1~ đến ~N~ theo thứ tự từ trên xuống dưới, các cột được đánh số từ ~1~ đến ~M~ theo thứ tự từ trái sang phải. Ban đầu, các ô trong bảng đều có giá trị là ~0~.

Có ~Q~ truy vấn, mỗi truy vấn thuộc một trong ba loại sau:

• ~1~ ~r~ ~x~: tăng giá trị của tất cả các ô trong dòng ~r~ thêm ~x~.
• ~2~ ~c~ ~x~: tăng giá trị của tất cả các ô trong cột ~c~ thêm ~x~.
• ~3~ ~x_1~ ~y_1~ ~x_2~ ~y_2~: tìm giá trị lớn nhất của các ô trong hình chữ nhật con có góc trái trên là ô ~(x_1, y_1)~ và góc phải dưới là ô ~(x_2, y_2)~. Nói cách khác, nếu gọi ~A_{i,j}~ là giá trị của ô ~(i, j)~ thì truy vấn này yêu cầu tìm:

\[\displaystyle\max_{\substack{x_1 \le i \le x_2 \\ y_1 \le j \le y_2}} A_{i,j}\]

Hãy viết chương trình xử lí ~Q~ truy vấn trên.

Input

• Dòng đầu tiên gồm ba số nguyên ~N~, ~M~, ~Q~ ~(1 \le N, M \le 2000,~ ~1 \le Q \le 15000)~ - số dòng, số cột của bảng số và số truy vấn.
• ~Q~ dòng tiếp theo, mỗi dòng mô tả một truy vấn thuộc một trong ba dạng trên:
  • Với truy vấn loại ~1~: ~1 \le r \le N,~ ~1 \le x \le 10^9~
  • Với truy vấn loại ~2~: ~1 \le c \le M,~ ~1 \le x \le 10^9~
  • Với truy vấn loại ~3~: ~1 \le x_1 \le x_2 \le N,~ ~1 \le y_1 \le y_2 \le M~

Output

• Với mỗi truy vấn loại ~3~, in ra một dòng gồm một số nguyên duy nhất là giá trị lớn nhất cần tìm.

Samples

Sample Input 1

3 4 6
2 4 5
3 1 3 3 4
1 1 4
2 2 3
3 1 1 2 3
3 2 1 3 1

Sample Output 1

5
7
0

Clarification

Hình vẽ minh họa cho test ví dụ:

• Ban đầu

  

• Sau truy vấn thứ nhất. Vùng màu xanh là dòng (hoặc cột) được mô tả trong truy vấn.

  

• Truy vấn thứ hai. Vùng màu vàng là hình chữ nhật con được mô tả trong truy vấn.

  

• Sau truy vấn thứ ba

  

• Sau truy vấn thứ tư

  

• Truy vấn thứ năm

  

• Truy vấn thứ sáu

  

Scoring

• Subtask ~1~ (~50\%~ số điểm): ~N, M \le 200,~ ~Q \le 1500~
• Subtask ~2~ (~50\%~ số điểm): Không có ràng buộc gì thêm