Cube Dividing

Time Limit : 5 sec, Memory Limit : 524288 KB

Cube Dividing

Pablo Cubarson is a well-known cubism artist. He is producing a new piece of work using a cuboid which consists of $A \times B \times C$ unit cubes. He plans to make a beautiful shape by removing $N$ units cubes from the cuboid. When he is about to begin the work, he has noticed that by the removal the cuboid may be divided into several parts disconnected to each other. It is against his aesthetics to divide a cuboid. So he wants to know how many parts are created in his plan.

Your task is to calculate the number of connected components in the cuboid after removing the $N$ cubes. Two cubes are connected if they share one face.


The input consists of a single test case. The test case is formatted as follows:

$A$ $B$ $C$ $N$
$X_1$ $Y_1$ $Z_1$
$X_N$ $Y_N$ $Z_N$

The first line contains four integers $A$, $B$, $C$ and $N$. $A$, $B$ and $C$ ($1 \leq A,B,C \leq 10^6$) denote the size of the cuboid $-$ the cuboid has an $A$ unit width from left to right and a $B$ unit height from bottom to top, and a $C$ unit depth from front to back. $N$ ($0 \leq N \leq 20,000, N \leq A \times B \times C - 1$) denotes the number of the cubes removed in the Cubarson's plan. Each of the following $N$ lines contains three integers $X_i$ ($0 \leq X_i \leq A-1$), $Y_i$ ($0 \leq Y_i \leq B-1$) and $Z_i$ ($0 \leq Z_i \leq C - 1$). They denote that the cube located at the $X_i$-th position from the left, the $Y_i$-th from the bottom and the $Z_i$-th from the front will be removed in the plan. You may assume the given positions are distinct.


Print the number of the connected components in the cuboid after removing the specified cubes.

Sample Input 1

2 2 2 4
0 0 0
1 1 0
1 0 1
0 1 1

Output for the Sample Input 1


Sample Input 2

3 3 3 1
1 1 1

Output for the Sample Input 2


Sample Input 3

1 1 3 2
0 0 0
0 0 2

Output for the Sample Input 3


Source: JAG Practice Contest for ACM-ICPC Asia Regional 2015 , Japan, 2015-11-22