Задача №2773. Мобильные телефоны
Предположим, что в регионе Тампере базовые станции обеспечения мобильной телефонной связи четвертого поколения действуют следующим образом. Регион поделен на квадраты. Квадраты образуют матрицу размера \(S \times S\), строки и столбцы которой пронумерованы от \(0\) до \(S - 1\). В каждом квадрате находится базовая станция. Количество работающих мобильных телефонов внутри квадрата может меняться, так как телефоны могут перемещаться из одного квадрата в другой, и телефоны могут включаться или выключаться. В некоторые моменты времени каждая базовая станция передает головной базовой станции отчет об изменении количества работающих телефонов и свои координаты (номер строки и номер столбца соответственно).
Напишите программу, которая получает эти отчеты и отвечает на запросы о текущем общем количестве работающих мобильных телефонов в некоторой прямоугольной области.
Входные данные кодируются следующим образом. Каждая строка содержит одну команду. Команда состоит из кода и набора параметров (целых чисел) в соответствии со следующей таблицей:
| Команда | Параметры | Значение |
| 0 | S | Инициализирует матрицу размера \(S \times S\) нулями. Эта команда выдается только один раз и всегда будет первой командой. |
| 1 | X Y A | Прибавляет к количеству работающих мобильных телефонов в квадрате \((X, Y)\) число \(A\). Число \(A\) может быть как положительным, так и отрицательным. |
| 2 | L B R T | Запрашивает текущее суммарное количество работающих мобильных телефонов в квадратах \((X, Y)\), где \(L \leq X \leq R\), \(B \leq Y \leq T\). |
| 3 | Завершает программу. Эта команда выдается только один раз и всегда будет последней. |
Значения всегда будут в допустимых пределах, так что нет необходимости их проверять. В частности, добавление отрицательного числа A не приведет к уменьшению количества телефонов в квадрате до значения, меньшего нуля. Индексы в матрице начинаются от 0, например, для матрицы \(4 \times 4\), мы имеем \(0 \leq X \leq 3\) и \(0 \leq Y \leq 3\).
Ограничения: \(1 \leq S \leq 1024\), количество работающих телефонов в любом квадрате в любой момент времени \(0 \leq V \leq 2^{15} - 1\), изменение количества телефонов в квадрате матрицы \(-2^{15} \leq A \leq 2^{15} - 1\), количество команд во вводе \(3 \leq U \leq 60002\), суммарное количество телефонов во всей матрице \(0 \leq M \leq 2^{30}\).
Для каждой команды с кодом 2 ваша программа должны выдать в выходной файл одно число ответ на запрос
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
0 1 1 0 0 28766 2 0 0 0 0 1 0 0 -2826 2 0 0 0 0 1 0 0 -587 2 0 0 0 0 1 0 0 1017 2 0 0 0 0 1 0 0 -17234 2 0 0 0 0 1 0 0 19618 2 0 0 0 0 1 0 0 -2237 2 0 0 0 0 1 0 0 -9192 2 0 0 0 0 1 0 0 -11132 2 0 0 0 0 1 0 0 1842 2 0 0 0 0 3
28766 25940 25353 26370 9136 28754 26517 17325 6193 8035