Description

There is a solid glass cuboid with length, width, and height equal to $w, x, h$. It can be considered as being made up of many $1\times1\times1$ small cubes, and each small cube has coordinates $(i, j, k)$. Now we need to perform $q$ cuts. Each cut gives six parameters $(x_1, y_1, z_1), (x_2, y_2, z_2)$, and it is guaranteed that $x_1 \le x_2$, $y_1 \le y_2$, $z_1 \le z_2$. During each cut, a laser tool is used to carve out a cuboid cavity whose faces are parallel to the faces of the original cuboid. The two diagonal corner points of the cavity are exactly the two points given in the parameters.

In other words, all small cubes $(i, j, k)$ satisfying $x_1 \le i \le x_2$, $y_1 \le j \le y_2$, $z_1 \le k \le z_2$ will be evaporated by the laser. For example, for a $4\times4\times4$ large cube with volume $64$, if the parameters are $(1, 1, 1), (2, 2, 2)$, then the $8$ small cubes in the middle will be evaporated, leaving $56$ small cubes. Now, after all cutting operations, how many unit cubes of volume remain in the craft?

Input Format

The first line contains three positive integers $w, x, h$.

The second line contains one positive integer $q$.

The next $q$ lines each contain six integers $(x_1, y_1, z_1), (x_2, y_2, z_2)$.

Output Format

Output one integer representing the answer.

4 4 4
1
1 1 1 2 2 2

56

Hint

Constraints: $1 \le w, x, h \le 20$, $1 \le q \le 100$. $1 \le x_1 \le x_2 \le w$, $1 \le y_1 \le y_2 \le x$, $1 \le z_1 \le z_2 \le h$.

Translated by ChatGPT 5