Є квадратне поле, що складається з \(NxN\) клітинок. Спочатку в кожній клітині записано значення нуль. Напишіть програму, яка вміє ефективно відповідати на такі запити:

ADD x y — змільшити значення в клітинці x,y на 1.
GET x1 y1 x2 y2 — знайти суму значень в прямокутнику з кутами в x1,y1 та x2,y2 відповідно.

Формат вхідних даних

В першому рядку два числа \(N\) та \(K\) - розмір дошки, та число запитів. (\(1 \le N \le 1000\)), (\(1 \le K \le 300000\)) Наступні \(K\) рядків містять самі запити.

Формат вихідних даних

Для кожного запиту типу GET виведіть в окремому рядку ціле число - відповідь на запит.

Приклад вхідних даних

5 15
ADD 1 1
ADD 2 2
ADD 3 3
ADD 4 4
ADD 5 5
ADD 1 5
ADD 2 4
ADD 3 3
ADD 4 2
ADD 5 1
GET 1 1 5 5
GET 2 1 5 5
GET 1 2 5 5
GET 2 2 4 4
GET 3 3 3 3

Приклад вихідних даних

10
8
8
6
2