Bình đang thiết kế một bảng điều khiển đèn LED ma trận gồm \(N\) hàng và \(M\) cột. Ban đầu, tất cả các bóng đèn đều có độ sáng bằng \(0\). Bình thực hiện kiểm tra hoạt động của bảng LED qua \(Q\) thao tác:

• 1 x y val: Bình thay đổi độ sáng của bóng đèn tại tọa độ hàng \(x\) và cột \(y\) thành giá trị \(val\).
• 2 x1 y1 x2 y2: Bình đo tổng độ sáng của toàn bộ các bóng đèn nằm trong vùng hình chữ nhật giới hạn từ hàng \(x_1\) đến hàng \(x_2\), và từ cột \(y_1\) đến cột \(y_2\).

Hãy giúp Bình tính toán nhanh để kiểm nghiệm bảng LED hoạt động chính xác.

Định dạng đầu vào

• Dòng đầu chứa ba số nguyên dương \(N, M\) và \(Q\) (\(1 \le N, M \le 500\), \(1 \le Q \le 5 \cdot 10^4\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa thông tin của một thao tác theo một trong hai định dạng trên (\(1 \le x, x_1, x_2 \le N\), \(1 \le y, y_1, y_2 \le M\), \(0 \le val \le 10^9\)).

Định dạng đầu ra

• Với mỗi thao tác loại 2, in ra tổng độ sáng tìm được.

Ví dụ

Input:

3 3 3
1 1 1 5
1 2 2 10
2 1 1 2 2

Output:

15