Задача №111778. Мобильные телефоны
В области Тампере существуют станции обслуживания мобильных телефонов четвертого поколения, которые работают следующим образом. Вся область разделена на квадраты. Квадраты формируют матрицу S×S, строки и столбы которой нумеруются с 0 до S - 1. Каждый квадрат содержит одну станцию обслуживания. Количество активных мобильных телефонов внутри квадрата может меняться, потому что телефон может перемещаться из одного квадрата в другой или выключаться. Временами каждая станция обслуживания передает сведения об изменении в количестве активных телефонов на главную станцию обслуживания (вместе с номером строки и столбца матрицы).
Напишите программу, которая принимает эти сведения и отвечает на запросы о текущем количестве активных мобильных телефонов в любой прямоугольной области.
Каждый запрос к программе описывается на отдельной строке и состоит из одного целого числа, описывающего команду, а также из дополнительных параметров команды в соответствии со следующей таблицой:
| Команда | Параметры | Значение |
|---|---|---|
| 0 | S | Инициализирует матрицу размером S×S, состоящую только из нулей. Эта команда поступает один раз и является самой первой командой. |
| 1 | X Y A | Добавить число A к количеству активных мобильных телефонов в квадрате (X;Y). Число A может быть как положительным, так и отрицательным. |
| 2 | L B R T | Выдать текущую сумму количеств активных мобильных телефонов во всех квадратах (X;Y), где L ≤ X ≤ R, B ≤ Y ≤ T. |
| 3 | Прервать программу. Эта команда поступает один раз и является самой последней командой. |
Все значения всегда лежат в правильном диапазоне, поэтому нет необходимости их проверять. В частности, если число A отрицательное, то число активных телефонов в каком-либо квадрате все равно не станет меньше нуля. Индексы начинаются с 0, поэтому, например, для таблицы размера 4×4 имеем 0 ≤ X ≤ 3, 0 ≤ Y ≤ 3.
Ваша программа не должна отвечать ни на какую команду, кроме 2. Если команда 2, то ваша программа должна вывести единственную строку, содержащую одно целое число — ответ на этот запрос.
Ограничения
| Размер таблицы | S×S | 1×1 ≤ S×S ≤ 1024×1024 |
| Значение ячейки в любой момент времени | V | 0 ≤ V ≤ 215 - 1 (= 32767) |
| Величина обновления | A | -215 ≤ A ≤ 215 - 1 (= 32767) |
| Количество команд | U | 3 ≤ U ≤ 60002 |
| Максимальное количество активных телефонов во всей таблице | M | M = 230 |
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