[传智杯 #5 初赛] H-二人的世界

莲子设计了一个三维立体空间软件。这个软件可以模拟真实的物理引擎，包括实体方块和水流方块。然而，同时计算大量水流会对软件造成不小的负荷。 于是，莲子希望找到这样一种算法，快速计算这些水流模拟后的结果。

莲子设计的水流模型是这样的： 考虑一个三维空间。这个空间内有 $n$ 个正方体。我们使用坐标 $(x_i,y_i,h_i)$ 描述每个正方体的位置。这些正方体，可以被称作**实体方块**。  现在将会在这张图中模拟一种水流机制。具体而言，我们会定义**水方块**。水方块会有一个强度 $s$，范围是 $[1,k]$。 ### 运行逻辑 - 假定 $(x,y,h)$ 处有强度为 $s$ 的水方块，且 $(x,y,h-1)$ 位置没有实体方块，那么下一时刻 $(x,y,h-1)$ 位置会生成强度为 $k$ 的水方块。**注意**：无论此时 $s$ 的值是多少，在 $(x,y,h-1)$ 位置生成的水方块的强度都是 $k$。 - 假定 $(x,y,h)$ 处有强度为 $s$ 的水方块，且 $s>1$，且 $(x,y,h-1)$ 位置有实体方块，那么会进行**扩散操作**。 - 如果下一时刻，某个位置 $(x,y,h)$ 同时有多个水方块会生成，那么最终生成的水方块的强度，是这些可能生成的水方块里，最大的强度。   ### 扩散操作 **考虑到扩散操作比较抽象，建议结合图示理解**。 对于水方块 $(x,y,h)$，它会在高度 $h$ 的平面上进行寻路。为了考虑这个过程，我们考虑这个高度为 $h$ 的平面： - 如果空间里 $(x,y,h)$ 位置有实体方块存在，那么平面上 $(x,y)$ 处**不可经过**。否则，如果没有实体方块，那么 $(x,y)$ 处**可以经过**。 - 在 $(x,y)$ **可以经过**的情况下，如果空间里 $(x,y,h-1)$ 位置没有实体方块存在，那么平面上 $(x,y)$ 位置称为**目标位置**。目标位置可以不止一个。 根据扩散的前提条件，可知平面上 $(x,y)$ 位置可以经过，但不是目标位置。 从平面上 $(x,y)$ 处出发，进行路径的搜索。每次在 $(a,b)$ 位置会向 $(a+1,b),(a-1,b),(a,b+1),(a,b-1)$ 位置扩展。搜索过程会找到距离 $(x,y)$ 位置**最近**的，且距离不超过 $s-1$ 的**所有**目标位置，或者找不到这样的目标位置。 - 如果存在这样的目标位置，那么在到达目标位置的最短路的方向上，下一时刻会生成一个强度为 $s-1$ 的水方块。 - 如果不存在这样的目标位置，那么下一时刻，会向 $(x+1,y),(x-1,y),(x,y+1),(x,y-1)$ 位置都生成强度为 $s-1$ 的水方块（如果这个位置可以到达的话）。 请结合图示理解扩散过程。  如图所示。$S$ 处是平面上该水方块所在的位置。白色的方块是目标位置，打 $\times$ 的方块是不可经过的位置。我们计算出 $S$ 到达最近的目标位置的最小值 $d_{\min}=5$，图中标出来的**红色路径**就是三条可能的最短路。 如果 $s>5$，那么下一时刻，在**蓝色箭头**处会有强度为 $s-1$ 的水方块生成。否则，若 $5\ge s>1$，那么下一时刻除了蓝色箭头外，灰色路径对应的方向**也会生成**强度为 $s-1$ 的水方块。 --- 为了检验水流模型的合理性以及其运行效率，莲子提出了这个问题：在 $(x_0,y_0,10^9+1)$ 处，有一个强度为 $k$ 的水方块。询问：在经过充分长的时间后（比如经过了 $10^{9961^{9961}}$ 时刻），有多少个点对 $(a,b)$，满足在 $(a,b,-1)$ 位置，会有水方块生成过。

- 第一行有两个正整数 $n,k$ 和两个整数 $x_0,y_0$，描述实体方块的个数、水方块最大强度，以及初始水方块的位置。 - 接下来 $n$ 行，每行三个整数 $x_i,y_i,h_i$，描述每个实体方块的位置。保证不存在两个位置完全相同的实体方块。

- 输出共一行一个整数，表示有多少个点对 $(a,b)$，使得充分长时间后 $(a,b,-1)$ 位置有水方块生成过。

8 3 3 4
4 3 1
4 4 1
3 3 2
3 4 2
4 5 2
5 4 2
2 4 3
4 1 4

3

8 2 3 4
4 3 1
4 4 1
3 3 2
3 4 2
4 5 2
5 4 2
2 4 3
4 1 4

1

### 样例 1 解释 （图片实在太难画啦，将就一下吧。）为了防止方块阻挡导致看不见，方块全部换成了透明的。  初始状态下一根水流柱从高空落下，落在了方块 $(3,4,2)$ 上，进行了扩散。水方块的坐标为 $(3,4,3)$，强度为 $3$。  - 如图 $3$，根据寻路机制，它会在 $(3,5,3)$ 和 $(4,4,3)$ 上生成强度为 $2$ 的水方块。 - 如图 $4$，生成的两个支流下方都没有方块，于是在 $(3,5,2)$ 和 $(4,4,2)$ 上生成强度为 $3$ 的水方块。 - 如图 $5$，水方块 $(3,5,2)$ 下方依旧没有实体方块，于是在 $(3,5,1)$ 生成了强度为 $3$ 的水方块，一直流到 $(3,5,-1)$；水方块 $(4,4,2)$ 下方有实体方块，于是在 $(4,3,2)$ 生成了强度为 $2$ 的水方块。  下面只关心水方块 $(4,3,2)$。它下面有实体方块 $(4,3,1)$，于是它向两边扩散，生成强度均为 $1$ 的两个水方块。这两个方块下面都不再有实体方块，于是**一直往下流**到 $(4,2,-1)$ 和 $(5,3,-1)$。 因此，最终一共会有三个位置 $(3,5,-1)$、$(4,2,-1)$、$(5,3,-1)$ 有水方块经过。 ### 数据范围及约定 对于所有数据，$1\le n\le 10^5$，$1\le k\le 10^9$，$0\le |x_i|,|y_i|\le 10^9$，$0\le h_i\le 10^9$。