Problems
Dima and table
Dima and table
Мама подарила мальчику Диме таблицу размера \textbf{m}×\textbf{n}. Таблица эта не простая, а особенная. Дима может выбрать три числа --- \textbf{i}, \textbf{j} и \textbf{d} (\textbf{1} ≤ \textbf{i} ≤ \textbf{n}, \textbf{1} ≤ \textbf{j} ≤ \textbf{m}, \textbf{-1000} ≤ \textbf{d} ≤ \textbf{1000}), и к элементу с индексом (\textbf{i}, \textbf{j}) магически прибавится \textbf{d}. Дима играет со своим массивом, а мама время от времени задает ему вопросы --- какова сумма всех элементов, индексы которых удовлетворяют неравенствам \textbf{from_row} ≤ \textbf{row} ≤ \textbf{to_row} и \textbf{from_column} ≤ \textbf{column} ≤ \textbf{to_column}? Дима легко справился с этими вопросами, сможете ли вы?
\InputFile
В первой строке находятся три целых числа \textbf{n}, \textbf{m} и \textbf{q} (\textbf{1} ≤ \textbf{n}, \textbf{m} ≤ \textbf{1000}, \textbf{1} ≤ \textbf{q} ≤ \textbf{10^5}) --- количество строк и столбцов в таблице и суммарное количество операций и запросов соответственно. В следующих \textbf{n} строках дано по \textbf{m} чисел по модулю не более \textbf{1000} --- начальное состояние таблицы. В следующих \textbf{q} строках заданы операции и запросы. Первый символ в строке может быть \textbf{+} или \textbf{?}. Если строка начинается с \textbf{+}, то это операция прибавления. Далее следуют \textbf{i}, \textbf{j} и \textbf{d}, ограничения на которые описаны в условии. Если строка начинается с \textbf{?}, то это запрос. Далее следуют числа \textbf{from_row}, \textbf{to_row}, \textbf{from_column} и \textbf{to_column} (\textbf{1} ≤ \textbf{from_row} ≤ \textbf{to_row} ≤ \textbf{n}, \textbf{1} ≤ \textbf{from_column} ≤ \textbf{to_column} ≤ \textbf{n}).
\OutputFile
Ответы на запросы по одному в строке.
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