E. Инна и большая матрица конфет
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Инна очень любит сладкое. Поэтому она хочет сыграть в игру «Матрица конфет» с Димой и Сережей. Но Сережа очень большой, и игра для него оказалась маленькой. Сережа предложил поиграть в «Большую матрицу конфет».

Поле для игры «Большая матрица конфет» — это матрица размера n × m. Будем нумеровать строки матрицы от 1 до n, а столбцы — от 1 до m. Ячейку в i-ой строке и j-ом столбце будем обозначать (i, j). В каждой ячейке матрицы может лежать несколько конфет, изначально все ячейки пустые. Игра происходит в w ходов, на каждом ходу происходит одно из двух следующих событий:

  1. Сережа выбирает пять целых чисел x1, y1, x2, y2, v (x1 ≤ x2; y1 ≤ y2) и в каждую ячейку матрицы (i, j) (x1 ≤ i ≤ x2; y1 ≤ j ≤ y2) докладывает v конфет.
  2. Сережа выбирает четыре целых числа x1, y1, x2, y2 (x1 ≤ x2; y1 ≤ y2). Затем он просит Диму посчитать суммарное количество конфет в ячейках (i, j) (x1 ≤ i ≤ x2; y1 ≤ j ≤ y2), а Инну просит посчитать суммарное количество конфет в ячейках матрицы (p, q), которые удовлетворяют логическому условию: (p < x1 ИЛИ p > x2) И (q < y1 ИЛИ q > y2). Наконец, Сережа просит записать на листке разность числа, посчитанного Димой, и числа, посчитанного Инной (Д - И).

К сожалению, матрица Сережи оказалось воистину огромной. Поэтому Инна и Дима не справляются с подсчетом. Помогите им!

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

Первая строка входных данных содержит три целых числа n, m и w (3 ≤ n, m ≤ 4·106; 1 ≤ w ≤ 105).

Следующие w строк описывают ходы, которые были совершены в игре.

  • Строка, описывающая событие первого типа, содержит 6 целых чисел: 0, x1, y1, x2, y2 и v (1 ≤ x1 ≤ x2 ≤ n; 1 ≤ y1 ≤ y2 ≤ m; 1 ≤ v ≤ 109).
  • Строка, описывающая событие второго типа, содержит 5 целых чисел: 1, x1, y1, x2, y2 (2 ≤ x1 ≤ x2 ≤ n - 1; 2 ≤ y1 ≤ y2 ≤ m - 1).

Гарантируется, что хотя бы раз произойдет ход второго типа. Гарантируется, что ни одна операция добавления конфет в матрицу не добавляет больше 109 конфет в матрицу за раз.

Обратите внимание, что ограничения на входные данные в задаче достаточно большие, поэтому, пожалуйста, используйте оптимальные структуры данных. Максимальные тесты добавлены в претесты.

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

Для каждого хода второго типа выведите в отдельной строке целое число — разность между числами Димы и Инны.

Примеры
Входные данные
4 5 5
0 1 1 2 3 2
0 2 2 3 3 3
0 1 5 4 5 1
1 2 3 3 4
1 3 4 3 4
Выходные данные
2
-21
Примечание

Пояснение к примеру. После первого запроса матрица принимает вид:


22200
22200 
00000
00000

После второго:


22200
25500
03300 
00000

После третьего:


22201
25501
03301
00001

Для четвертого запроса сумма Димы равна 5 + 0 + 3 + 0 = 8, а сумма Инны равна 4 + 1 + 0 + 1 = 6. Ответ на запрос равен 8 - 6 = 2. Для пятого запроса сумма Димы равна 0, а сумма Инны равна 18 + 2 + 0 + 1 = 21. Ответ на запроса равен 0 - 21 = -21.