题目背景

莲子设计了一个三维立体空间软件。这个软件可以模拟真实的物理引擎，包括实体方块和水流方块。然而，同时计算大量水流会对软件造成不小的负荷。

于是，莲子希望找到这样一种算法，快速计算这些水流模拟后的结果。

题目描述

莲子设计的水流模型是这样的：

考虑一个三维空间。这个空间内有 $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$。