Vasya is a ufologist and his duties include
observing Unidentified Flying Objects (UFOs)
in the part of space bounded by a cube
N ×
N ×
N.
The cube is divided into cubic sectors 1 × 1 × 1.
During the observation, the following events may happen:
- several new UFOs emerge in a certain sector;
- several UFOs disappear in a certain sector;
- Vasya's boss may ask him how many UFOs there
are in a part of space consisting of several sectors.
At the moment when Vasya starts his observations there are no
UFOs in the whole space.
Input
The first line contains an integer N (1 ≤ N ≤ 128).
The coordinates of sectors are integers from 0 to N–1.
Then there are entries describing events, one entry per line.
Each entry starts with a number
M.
- If M is 1, then this number is followed by four
integers
x (0 ≤ x < N), y (0 ≤ y < N),
z (0 ≤ z < N), K (–20000 ≤
K ≤ 20000),
which are coordinates of a sector and the change
in the number of UFOs in this sector.
The number of UFOs in a sector cannot become negative.
- If M is 2, then this number is followed by
six integers
x1, y1, z1,
x2, y2, z2
(0 ≤ x1 ≤ x2 < N,
0 ≤ y1 ≤ y2 < N, 0 ≤
z1 ≤ z2 < N),
which mean that Vasya must compute the total number of UFOs
in sectors (x, y, z) belonging to the volume:
x1 ≤ x ≤ x2,
y1 ≤ y ≤ y2,
z1 ≤ z ≤ z2.
- If M is 3, it means that Vasya is tired and goes to
sleep. This entry is always the last one.
The number of entries does not exceed 100002.
Output
For each query, output in a separate line the required number of UFOs.
Sample
| input | output |
|---|
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
| 0
1
4
2
|
Problem Author: Dmitry Zhukov
Problem Source: Ural SU and Orel STU Contest. Petrozavodsk Summer Session, August 2006
