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