Giả sử các trạm gốc điện thoại di động thế hệ thứ tư ở khu vực Tampere hoạt động như sau. Khu vực được chia thành các ô vuông tạo thành ma trận \(S\times S\), có hàng và cột đánh số từ \(0\) đến \(S-1\). Mỗi ô chứa một trạm gốc.

Số điện thoại đang hoạt động trong một ô có thể thay đổi vì điện thoại di chuyển, được bật hoặc được tắt. Mỗi trạm thỉnh thoảng báo độ thay đổi cùng tọa độ ô của mình cho trạm chính. Hãy xử lý các báo cáo này và trả lời tổng số điện thoại đang hoạt động trong những vùng hình chữ nhật được hỏi.

Dữ liệu vào

Mỗi dòng chứa một lệnh và các tham số nguyên theo bảng sau:

Tất cả giá trị đều hợp lệ. Đặc biệt, một cập nhật âm không làm giá trị ô trở thành âm. Chỉ số bắt đầu từ 0; chẳng hạn, với \(S=4\), có \(0\le X,Y\le3\).

Dữ liệu ra

Với mỗi lệnh 2, in một dòng chứa một số nguyên là tổng được hỏi. Không in gì cho các lệnh khác.

Ràng buộc

• \(1\le S\le1024\).
• Giá trị \(V\) của mỗi ô tại mọi thời điểm: \(0\le V\le2^{15}-1=32767\).
• Độ thay đổi: \(-2^{15}\le A\le2^{15}-1\).
• Số lệnh \(U\): \(3\le U\le60002\).
• Tổng số điện thoại trong toàn bảng không vượt quá \(2^{30}\).
• Trong 20 bộ kiểm tra, có 16 bộ với \(S\le512\).

Giới hạn bộ nhớ của kỳ thi gốc là 5 MiB; bản luyện tập này dùng 8 MiB để phù hợp với môi trường chạy hiện nay. Giới hạn thời gian vẫn là 1 giây.

Chấm điểm

Mỗi bộ kiểm tra tương ứng 5 điểm trong thang điểm gốc 100; kết quả đúng và trong giới hạn thời gian nhận toàn bộ điểm của bộ đó.

Lưu ý vào ra

Đọc từ đầu vào chuẩn và ghi ra đầu ra chuẩn. Đề gốc yêu cầu đẩy dữ liệu sau mỗi câu trả lời: với C++, có thể dùng cout << answer << endl << flush;; với C, dùng printf("%d\n", answer); fflush(stdout);. Với Pascal, đọc bằng Read(last); ... Readln; và ghi bằng Writeln(answer);. Công cụ kiểm tra trực tuyến gốc chuyển tệp đầu vào vào đầu vào chuẩn của chương trình.

Ví dụ

0 4
1 1 2 3
2 0 0 2 2
1 1 1 2
1 1 2 -1
2 1 1 2 3
3

3
4

Nguồn

Đề gốc IOI 2001. Bảng tổng quan ngày 1.