eolymp
bolt
Try our new interface for solving problems
Problems

Dima and table

Dima and table

Time limit 2 seconds
Memory limit 256 MiB

Мама подарила мальчику Диме таблицу размера m×n. Таблица эта не простая, а особенная. Дима может выбрать три числа — i, j и d (1in, 1jm, -1000d1000), и к элементу с индексом (i, j) магически прибавится d. Дима играет со своим массивом, а мама время от времени задает ему вопросы — какова сумма всех элементов, индексы которых удовлетворяют неравенствам from_rowrowto_row и from_columncolumnto_column? Дима легко справился с этими вопросами, сможете ли вы?

Input data

В первой строке находятся три целых числа n, m и q (1n, m1000, 1q10^5) — количество строк и столбцов в таблице и суммарное количество операций и запросов соответственно. В следующих n строках дано по m чисел по модулю не более 1000 — начальное состояние таблицы. В следующих q строках заданы операции и запросы. Первый символ в строке может быть + или ?. Если строка начинается с +, то это операция прибавления. Далее следуют i, j и d, ограничения на которые описаны в условии. Если строка начинается с ?, то это запрос. Далее следуют числа from_row, to_row, from_column и to_column (1from_rowto_rown, 1from_columnto_columnn).

Output data

Ответы на запросы по одному в строке.

Examples

Input example #1
3 3 5
1 2 3
4 5 6
7 8 9
? 1 3 1 3
+ 3 3 2
? 1 3 1 3
? 1 3 3 3
? 1 2 1 2
Output example #1
45
47
20
12
Author Egor Kulikov
Source Winter School Kharkov 2012