Tổng Trên Bảng Động

Description

Một bảng vuông $w\times w$ ban đầu chứa toàn số $0$, các hàng và cột được đánh số từ $1$ đến $w$. Bạn nhận một chuỗi lệnh theo thời gian: lệnh loại $1$ cộng một giá trị vào một ô; lệnh loại $2$ hỏi tổng hiện tại trên một hình chữ nhật đóng; lệnh $3$ kết thúc dữ liệu.

Input

• Dòng đầu là lệnh $0$ và kích thước $w$.
• Các dòng sau là lệnh cập nhật $1$ $x$ $y$ $a$, truy vấn $2$ $x_1$ $y_1$ $x_2$ $y_2$ hoặc lệnh kết thúc $3$.

Output

• Với mỗi truy vấn loại $2$, in tổng hiện tại trong hình chữ nhật đóng.

Constraints

• $1\le w\le 2\cdot 10^6$.
• Có không quá $1.6\cdot 10^5$ cập nhật và $10^4$ truy vấn.
• $1\le x,x_1,x_2,y,y_1,y_2\le w$; $x_1\le x_2$ và $y_1\le y_2$.
• $0\le a\le 10^9$; mọi kết quả nằm trong số nguyên $64$ bit có dấu.

Scoring

• Subtask $1$ ($50\%$ số điểm): dữ liệu nhỏ theo giới hạn được công bố trong hệ thống chấm.
• Subtask $2$ ($50\%$ số điểm): không có giới hạn bổ sung.

Example

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

3
10