Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P144SUMJ - ROUND 4J - Nuôi cấy vi khuẩn

Phòng thí nghiệm XYZ thực hiện nuôi cấy một loại vi khuẩn trên một bảng ô vuông kích thước n×n với các dòng và các cột đánh số từ 1 tới n. Số cá thể vi khuẩn trong một ô vuông ban đầu là 0 và người ta có thể tiến hành cấy thêm một số cá thể vi khuẩn trong mỗi ô.

Có hai loại yêu cầu:

* S x y a: Cấy thêm a cá thể vi khuẩn vào ô (x,y) (1 ≤ a ≤ 10^5);
* Q x_1 y_1 x_2 y_2: Yêu cầu cho biết tổng số cá thể vi khuẩn trong các ô (x,y) nằm trong phạm vi x_1 ≤ x ≤ x_2, y_1 ≤ y ≤ y_2.

Cho biết một dãy m yêu cầu thực hiện tuần tự, hãy trả lời tất cả các yêu cầu loại Q.

Input

Dòng 1 chứa hai số nguyên dương n, m ≤ 10^5;

m dòng tiếp theo, mỗi dòng chứa một yêu cầu theo thứ tự thực hiện.

Output

Ứng với mỗi chỉ thị Q, hãy in ra số lượng cá thể vi khuẩn tương ứng tính được.

Example

Input:
4 7
S 2 2 2
S 4 3 3
Q 2 2 4 4
S 1 2 5
S 4 3 6
Q 1 1 4 4
Q 1 1 2 2 Output: 5
16
7

Được gửi lên bởi:adm
Ngày:2014-07-17
Thời gian chạy:2s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP CPP C++ 4.3.2 CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.