eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків

НЛО

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

У обов'язки уфолога Васі входить спостереження за усіма неопізнаними літаючими об'єктами (НЛО) у частині простору, обмеженого кубом розміром N×N×N. Цей куб поділено на кубічні сектора розміром 1×1×1. Під час спостережень Васі можуть відбуватись наступні події:

  • у якомусь секторі з'являється декілька новых НЛО;

  • у якомусь секторі щезає декілька НЛО;

  • також йому може зателефонувати начальник і запитати, скільки НЛО у даний момент знаходиться у частині простору, який складається з декількох секторів.

У момент, коли Вася почав свої спостереженя, у всьому просторі не було жодного НЛО.

Вхідні дані

Перший рядок містить ціле число N (1N128). Координати кубічних секторів — цілі числа від 0 до N–1.

Далі йдуть записи про події, що відбуваються, по одному запису у кожному рядку. На початку рядка записано число M.

  • Якщо M дорівнює 1, то за ним йде 4 числа — x (0x < N), y (0y < N), z (0z < N), K (–20000K20000) — координати кубічного сектору і величина, на яку у ньому змінилась кількість НЛО. Після зміни кількість НЛО ні у якому секторі не може стати від'ємною.

  • Якщо M дорівнює 2, то за ним йде 6 чисел — x_1, y_1, z_1, x_2, y_2, z_2 (0x_1x_2 < N, 0y_1y_2 < N, 0z_1z_2 < N), які означають, що Васі наказано порахувати кількість НЛО у секторах (x, y, z) з області: x_1xx_2, y_1yy_2, z_1zz_2.

  • Якщо M дорівнює 3, то це значить, що Вася втомився спостерігати за НЛО і пішов спати. Цей запис зустрічається лише один раз і є останньою.

Кількість записів не перевищує 100002.

Вихідні дані

Для кожного питання виведіть у окремому рядку одне число — шукану кількість НЛО.

Приклад

Вхідні дані #1
1
1 0 0 0 10
1 0 0 0 15
2 0 0 0 0 0 0
1 0 0 0 -9
1 0 0 0 5
1 0 0 0 -10
2 0 0 0 0 0 0
1 0 0 0 -1
2 0 0 0 0 0 0
3
Вихідні дані #1
25
11
10
Автор Дмитро Жуков
Джерело Ural SU and Orel STU Contest. Petrozavodsk Summer Session, August 2006