Cube Dividing

Time limit5sMemory limit512 MB

Summary

Count the face-connected components of unit cubes left in an A x B x C box after removing N given cubes, where the box is huge but N is at most 20000.

Level: Hard8 of 10
Topics: Graph, BFS, DFS, Hash map
Solved: No attempts yet

Problem

Pablo Cubarson is a cubism artist. His new piece starts from a cuboid made of $A \times B \times C$ unit cubes. He plans to carve the shape he wants by removing $N$ of those unit cubes. Just before starting, he noticed that the removal can split the remaining material into several parts that no longer touch each other. A piece that falls apart into several parts goes against his sense of beauty, so he wants to know how many parts his plan produces.

Count the connected components formed by the unit cubes that remain after the $N$ cubes are removed. Two cubes are connected when they share a face.

Input

The input is a single test case in the following format.

A B C N
X1 Y1 Z1
...
XN YN ZN

The first line contains the integers $A$ , $B$ , $C$ and $N$ . $A$ , $B$ and $C$ ( $1 \le A, B, C \le 10^6$ ) give the size of the cuboid: it is $A$ units wide from left to right, $B$ units tall from bottom to top, and $C$ units deep from front to back. $N$ ( $0 \le N \le 20000$ , $N \le A \times B \times C - 1$ ) is the number of cubes that are removed.

Each of the next $N$ lines contains the integers $X_i$ ( $0 \le X_i \le A-1$ ), $Y_i$ ( $0 \le Y_i \le B-1$ ) and $Z_i$ ( $0 \le Z_i \le C-1$ ). They mean that the cube $X_i$ steps from the left, $Y_i$ steps from the bottom and $Z_i$ steps from the front is removed. Coordinates count from 0. All given positions are distinct.

Output

Print the number of connected components that remain after the listed cubes are removed.

Examples4

Example 1
Input
```
2 2 2 4
0 0 0
1 1 0
1 0 1
0 1 1
```
Expected output
```
4
```
Example 2
Input
```
3 3 3 1
1 1 1
```
Expected output
```
1
```
Example 3
Input
```
1 1 3 2
0 0 0
0 0 2
```
Expected output
```
1
```
Example 4
Input
```
1000000 1000000 1000000 0
```
Expected output
```
1
```