Задача №3013. Точки на плоскости
Есть квадратная клетчатая плоскость состоящая из n × n клеток (1 ≤ n ≤ 1000). Изначально в каждой клетке записано значение ноль. Ваша задача — написать программу, умеющую отвечать на следующие запросы:
- ADD x y — увеличить значение в ячейке x, y на 1.
- GET x1 y1 x2 y2 — вернуть сумму значений в прямоугольнике с углами в x1, y1 и x2, y2 соответственно.
Входные данные
В первой строке входного файла содержится два числа — n и k — размер доски и число запросов соответственно. Следующие k строк содержат сами запросы. Гарантируется, что общее число запросов не превосходит 300 000.
Выходные данные
Для каждого запроса типа 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
Сдать: для сдачи задач необходимо войти в систему