eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Звезды

Звезды

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Вася любит наблюдать за звездами. Но следить за всем небом сразу ему тяжело. Поэтому он наблюдает только за частью пространства, ограниченной кубом размером n×n×n. Этот куб поделен на маленькие кубики размером 1×1×1. Во время его наблюдений могут происходить следующие события:

  • В каком-то кубике появляются или исчезают несколько звезд.

  • К нему может заглянуть его друг Петя и поинтересоваться, сколько видно звезд в части пространства, состоящей из нескольких кубиков.

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

Первая строка входного файла содержит натуральное число 1n128. Координаты кубиков - целые числа от 0 до n-1. Далее следуют записи о происходивших событиях по одной в строке. В начале строки записано число m. Если m равно:

  • 1, то за ним следуют 4 числа - x, y, z (0x, y, z < n) и k (-20000k20000) - координаты кубика и величина, на которую в нем изменилось количество видимых звезд;

  • 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;

  • 3, то это означает, что Васе надоело наблюдать за звездами и отвечать на вопросы Пети. Эта запись встречается во входном файле только один раз и будет последней записью.

Количество записей во входном файле не больше 100002.

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

Для каждого Петиного вопроса выведите на отдельной строке одно число - искомое количество звезд.

Пример

Входные данные #1
2
2 1 1 1 1 1 1
1 0 0 0 1
1 0 1 0 3
2 0 0 0 0 0 0
2 0 0 0 0 1 0
1 0 1 0 -2
2 0 0 0 1 1 1
3
Выходные данные #1
0
1
4
2