问题陈述
Pablo Cubason 是一位著名的立体派艺术家。他正在使用一个长方体制作一件新作品,该长方体由 $A \times B \times C$ 单位立方体组成。他计划通过从长方体中移除 $N$ 单位的立方体来制作一个漂亮的形状。当他准备开始工作时,他注意到通过移除长方体可能会被分成几个彼此不相连的部分。分割长方体是违背他的审美的。所以他想知道他的计划中创造了多少个零件。
你的任务是计算移除$N$个立方体后长方体中连通分量的数量。如果两个立方体共享一个面,则它们是相连的。
输入
输入由单个测试用例组成。 测试用例的格式如下:
$A$$B$$C$$N$
$X_1$ $Y_1$ $Z_1$
...
$X_N$ $Y_N$ $Z_N$
第一行包含四个整数$A$、$B$、$C$ 和$N$。 $A$、$B$ 和 $C$ ($1 \leq A, B, C \leq 10^6$) 表示长方体的大小 --- 长方体从左到右的宽度为 $A$ 单位,从下到上的高度为 $B$ 单位,从前到后的深度为 $C$ 单位。 $N$ ($0 \leq N \leq 20{,}000$, $N \leq A \times B \times C - 1$) 表示 Cubarson 计划中移除的立方体数量。以下 $N$ 行中的每一行都包含三个整数 $X_i$ ($0 \leq X_i \leq A-1$)、$Y_i$ ($0 \leq Y_i \leq B-1$) 和 $Z_i$ ($0 \leq Z_i \leq C-1$)。它们表示位于从左侧第 $X_i$ 个位置、从底部第 $Y_i$ 个位置和从前面第 $Z_i$ 个位置的立方体将在计划中被删除。您可以假设给定的位置是不同的。
输出
打印移除指定立方体后长方体中连通分量的数量。
示例输入 1
2 2 2 4 0 0 0 1 1 0 1 0 1 0 1 1
样本输入 1 的输出
4
示例输入 2
3 3 3 1 1 1 1
样本输入 2 的输出
1
示例输入 3
1 1 3 2 0 0 0 0 0 2
样本输入 3 的输出
1