Tổng Trên Lưới

Một bảng vuông kích thước $S\times S$ lưu số thiết bị đang hoạt động tại từng ô. Ban đầu mọi ô đều bằng $0$. Bạn phải xử lý các lệnh cộng vào một ô và hỏi tổng trên một hình chữ nhật đóng; tọa độ hàng và cột đều bắt đầu từ $0$.

Input

• Lệnh đầu tiên có dạng $0$ $S$ để khởi tạo bảng.
• Sau đó là các lệnh $1$ $X$ $Y$ $A,2$ $L$ $B$ $R$ $T$ hoặc lệnh kết thúc $3$.
• Lệnh $1$ cộng $A$ vào ô $(X,Y)$. Lệnh $2$ hỏi tổng các ô có $L\le X\le R$ và $B\le Y\le T$.

Output

• Với mỗi lệnh loại $2$, in tổng cần tìm trên một dòng.

Constraints

• $1\le S\le 1024$.
• Tổng số lệnh, kể cả lệnh khởi tạo và kết thúc, nằm trong $[3,6\cdot 10^4+2]$.
• $0\le X,Y,L,B,R,T<S,L\le R,B\le T$.
• $-3.2768\cdot 10^4\le A\le 3.2767\cdot 10^4$; sau mỗi cập nhật, giá trị của ô thuộc $[0,3.2767\cdot 10^4]$.
• Tổng trên toàn bảng không vượt quá $2^{30}$.

Scoring

• Subtask $1$ ($50\%$ số điểm): $S\le 64$ và có không quá $2000$ lệnh.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

0 4
1 0 0 5
1 2 3 7
2 0 0 2 3
1 0 0 -2
2 0 0 0 0
3

12
3