#icpc2015autumng. [icpc2015autumn_g]Cube Dividing

[icpc2015autumn_g]Cube Dividing

MathJax.Hub.Config({ tex2jax: { inlineMath: [["","",""], ["\\(","\\)"]], processEscapes: true }}); blockquote { font-family: Menlo, Monaco, "Courier New", monospace; color: #333333; display: block; padding: 8.5px; margin: 0 0 9px; font-size: 12px; line-height: 18px; background-color: #f5f5f5; border: 1px solid #ccc; border: 1px solid rgba(0, 0, 0, 0.15); -webkit-border-radius: 4px; -moz-border-radius: 4px; border-radius: 4px; white-space: pre; white-space: pre-wrap; word-break: break-all; word-wrap: break-word; }

Problem Statement

Pablo Cubarson is a well-known cubism artist. He is producing a new piece of work using a cuboid which consists of AtimesBtimesCA \\times B \\times C unit cubes. He plans to make a beautiful shape by removing NN 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 NN cubes. Two cubes are connected if they share one face.


Input

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

AA BB CC NN
X_1X\_1 Y_1Y\_1 Z_1Z\_1
...
X_NX\_N Y_NY\_N Z_NZ\_N

The first line contains four integers AA, BB, CC and NN. AA, BB and CC (1leqA,B,Cleq1061 \\leq A, B, C \\leq 10^6) denote the size of the cuboid --- the cuboid has an AA unit width from left to right and a BB unit height from bottom to top, and a CC unit depth from front to back. NN (0leqNleq20,0000 \\leq N \\leq 20{,}000, NleqAtimesBtimesC1N \\leq A \\times B \\times C - 1) denotes the number of the cubes removed in the Cubarson’s plan. Each of the following NN lines contains three integers X_iX\_i (0leqX_ileqA10 \\leq X\_i \\leq A-1), Y_iY\_i (0leqY_ileqB10 \\leq Y\_i \\leq B-1) and Z_iZ\_i (0leqZ_ileqC10 \\leq Z\_i \\leq C-1). They denote that the cube located at the X_iX\_i-th position from the left, the Y_iY\_i-th from the bottom and the Z_iZ\_i-th from the front will be removed in the plan. You may assume the given positions are distinct.

Output

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

```plain
4```

* * *

### Sample Input 2

```plain
3 3 3 1
1 1 1```

### Output for the Sample Input 2

```plain
1```

* * *

### Sample Input 3

```plain
1 1 3 2
0 0 0
0 0 2```

### Output for the Sample Input 3

```plain
1```

* * *