ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Ural SU and Orel STU contest. Petrozavodsk training camp. Summer 2006

About     Problems     Submit solution     Judge status     Standings
Contest is over

C. UFOs

Time limit: 2.0 second
Memory limit: 64 MB
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 ≤ x1x2 < N, 0 ≤ y1y2 < N, 0 ≤ z1z2 < N), which mean that Vasya must compute the total number of UFOs in sectors (x, y, z) belonging to the volume: x1xx2, y1yy2, z1zz2.
  • 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

inputoutput
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
To submit the solution for this problem go to the Problem set: 1470. UFOs