Star Wars

Ariadne went on vacation to Disneyland in America. One day she visited Star Tours, which is dedicated to the Star Wars movies. There was a rectangular parallelepiped with sides X (length) × Y (width) × Z (height), consisting of cubes with sides equal to 1. Let's name each cube with its three coordinates, starting the numbering in each dimension from zero and going up to X-1, Y-1, and Z-1, respectively. Each cube is either bright or dark. By shooting a laser beam at a cube, it changes its state from bright to dark and vice versa. Initially, all cubes are dark.

Ariadne found a weapon capable of emitting "wide" laser beams, hitting entire levels with cubes simultaneously, in any dimension X, Y, or Z. Using it, Ariadne chooses a dimension (X, Y, or Z) and two numbers A and B. Then, all cubes with their coordinate in that dimension being between A and B (inclusive) are hit by the laser and change their state. For example, if she selects dimension X and A=2, B=3, then all cubes with their X coordinate equal to 2 or 3 will change state.

Ariadne uses the weapon many times, for various dimensions and various values of A and B. However, she wants to know at any time how many bright cubes exist in any section of the rectangular parallelepiped. Specifically, for each pair of coordinates (~x_1~, ~y_1~, ~z_1~) and (~x_2~, ~y_2~, ~z_2~), she wants to know the number of bright cubes in the rectangular parallelepiped with opposite vertices at the cubes with these coordinates.

Problem

Develop a program in one of the IOI languages (Pascal, C, C++, Java) that processes Ariadne's shots and answers her questions.

Input Files:

The input file named starwars.in is a text file where the first line contains an integer N, the number of Ariadne's trials. For each trial, a set of lines follows, where the first one contains four integers X, Y, Z, and M, separated in pairs by a single space. The first three are the sides of the rectangular parallelepiped in the three dimensions, and M is the number of actions that will follow. Each of the next M lines corresponds to an action. The actions are in the form:

• 0 A B: All cubes with X coordinate from A to B (inclusive) are hit by the laser (0 ~\le~ Α ~\le~ Β ~<~ Χ).
• 1 A B: All cubes with Y coordinate from A to B (inclusive) are hit by the laser (0 ~\le~ Α ~\le~ Β ~<~ Y).
• 2 A B: All cubes with Z coordinate from A to B (inclusive) are hit by the laser (0 ~\le~ Α ~\le~ Β ~<~ Z).
• 3 x~_1~ y~_1~ z~_1~ x~_2~ y~_2~ z~_2~: Ariadne asks how many bright cubes exist in the rectangular parallelepiped with opposite vertices at the cubes (x~_1~, y~_1~, z~_1~) and (x~_2~, y~_2~, z~_2~). Consider that 0 ~\le~ x1 ~\le~ x2 ~<~ Χ, and similarly for the other dimensions.

Note that for each trial, Ariadne starts with a rectangular parallelepiped of possibly different dimensions, where all cubes are dark.

Output Files:

The output file named starwars.out is a text file consisting of as many lines as there are questions in the input file. Each line will contain exactly one integer, the answer to the corresponding question.

Example of Input - Output Files:

STDIN (starwars.in)

2
2 2 2 5
0 0 0
1 1 1
3 0 0 0 1 1 1
2 1 1
3 0 0 0 0 1 1
4 5 6 6
0 2 2
0 2 3
1 3 3
3 0 0 0 2 3 3
2 0 3
3 1 1 1 2 2 2

STDOUT (starwars.out)

4
2
12
8

Explanation: For your convenience, the data for the two different trials are displayed separately. There will be no empty lines in the input/output files. In the first trial, the state of the cubes at the time of the two questions is shown in the images on the next page. In the first question, Ariadne asks for the number of all bright cubes in the left image (4). In the second question, she asks for the number of bright cubes with X coordinate = 0 in the right image (2).

Constraints:

For all test cases, it will be: 1 ~\le~ Ν ~\le~ 15.

• For test cases worth 20%, of the total points, it will be:
  1 ~\le~ X, Y, Z ~\le~ 100
  1 ~\le~ Μ ~\le~ 100
• For test cases worth 60%, of the total points, it will be:
  1 ~\le~ X, Y, Z ~\le~ 35.000
  1 ~\le~ Μ ~\le~ 4.000
• For test cases worth 100%, of the total points, it will be:
  1 ~\le~ X, Y, Z ~\le~ 100.000
  1 ~\le~ Μ ~\le~ 5.000

Formatting: In the output, each line terminates with a newline character.
Maximum execution time: 1 sec.
Maximum available memory: 64 MB.