eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Суммирование матрицы

Суммирование матрицы

Лимит времени 1 секунда
Лимит использования памяти 122 MiB

Матрица n × n заполнена числами. BuggyD анализирует матрицу и хочет найти сумму некоторых подматриц, то есть он хочет записать результаты своих запросов. Матрица динамическая, значение в любой ячейке может быть изменено.

В начале все ячейки матрицы заполнены 0. Разработайте программу для BuggyD.

Входные данные

Первая строка соержит количество тестов t.

Первая строка каждого теста содержит одно целое число n (1n1024) - размер матрицы.

Далее следует набор команд в одном из трех форматов:

  • "SET x y num" - установить значение ячейки (x, y) равной num (0x, y < n).

  • "SUM x1 y1 x2 y2" - найти сумму чисел в прямоугольнике от (x1, y1) до (x2, y2) включительно. Считайте, что x1x2 и y1y2, результат помещается в знаковое 64-битное целое.

  • "END" - указывает на конец теста.

Выходные данные

Для каждого запроса "SUM" выведите в отдельной строке ответ на него. после каждого теста выводите пустую строку.

Пример

Входные данные #1
1
4
SET 0 0 1
SUM 0 0 3 3
SET 2 2 12
SUM 2 2 2 2
SUM 2 2 3 3
SUM 0 0 2 2
END
Выходные данные #1
1
12
12
13