Инна очень любит сладкое. Поэтому она хочет сыграть в игру «Матрица конфет» с Димой и Сережей. Но Сережа очень большой, и игра для него оказалась маленькой. Сережа предложил поиграть в «Большую матрицу конфет».
Поле для игры «Большая матрица конфет» — это матрица размера n × m. Будем нумеровать строки матрицы от 1 до n, а столбцы — от 1 до m. Ячейку в i-ой строке и j-ом столбце будем обозначать (i, j). В каждой ячейке матрицы может лежать несколько конфет, изначально все ячейки пустые. Игра происходит в w ходов, на каждом ходу происходит одно из двух следующих событий:
- Сережа выбирает пять целых чисел x1, y1, x2, y2, v (x1 ≤ x2; y1 ≤ y2) и в каждую ячейку матрицы (i, j) (x1 ≤ i ≤ x2; y1 ≤ j ≤ y2) докладывает v конфет.
- Сережа выбирает четыре целых числа 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). Наконец, Сережа просит записать на листке разность числа, посчитанного Димой, и числа, посчитанного Инной (Д - И).
К сожалению, матрица Сережи оказалось воистину огромной. Поэтому Инна и Дима не справляются с подсчетом. Помогите им!
Выходные данные
Для каждого хода второго типа выведите в отдельной строке целое число — разность между числами Димы и Инны.
Примечание
Пояснение к примеру. После первого запроса матрица принимает вид:
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.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|