{"raw_statement":[{"iden":"background","content":"莲子设计了一个三维立体空间软件。这个软件可以模拟真实的物理引擎，包括实体方块和水流方块。然而，同时计算大量水流会对软件造成不小的负荷。\n\n于是，莲子希望找到这样一种算法，快速计算这些水流模拟后的结果。"},{"iden":"statement","content":"莲子设计的水流模型是这样的：\n\n考虑一个三维空间。这个空间内有 $n$ 个正方体。我们使用坐标 $(x_i,y_i,h_i)$ 描述每个正方体的位置。这些正方体，可以被称作**实体方块**。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/sotibgh2.png)\n\n现在将会在这张图中模拟一种水流机制。具体而言，我们会定义**水方块**。水方块会有一个强度 $s$，范围是 $[1,k]$。\n\n### 运行逻辑\n\n- 假定 $(x,y,h)$ 处有强度为 $s$ 的水方块，且 $(x,y,h-1)$ 位置没有实体方块，那么下一时刻 $(x,y,h-1)$ 位置会生成强度为 $k$ 的水方块。**注意**：无论此时 $s$ 的值是多少，在 $(x,y,h-1)$ 位置生成的水方块的强度都是 $k$。\n- 假定 $(x,y,h)$ 处有强度为 $s$ 的水方块，且 $s>1$，且 $(x,y,h-1)$ 位置有实体方块，那么会进行**扩散操作**。\n- 如果下一时刻，某个位置 $(x,y,h)$ 同时有多个水方块会生成，那么最终生成的水方块的强度，是这些可能生成的水方块里，最大的强度。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/mn8iqp4l.png)\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/suq9jiqx.png)\n\n### 扩散操作\n\n**考虑到扩散操作比较抽象，建议结合图示理解**。\n\n对于水方块 $(x,y,h)$，它会在高度 $h$ 的平面上进行寻路。为了考虑这个过程，我们考虑这个高度为 $h$ 的平面：\n\n- 如果空间里 $(x,y,h)$ 位置有实体方块存在，那么平面上 $(x,y)$ 处**不可经过**。否则，如果没有实体方块，那么 $(x,y)$ 处**可以经过**。\n- 在 $(x,y)$ **可以经过**的情况下，如果空间里 $(x,y,h-1)$ 位置没有实体方块存在，那么平面上 $(x,y)$ 位置称为**目标位置**。目标位置可以不止一个。\n\n根据扩散的前提条件，可知平面上 $(x,y)$ 位置可以经过，但不是目标位置。\n\n从平面上 $(x,y)$ 处出发，进行路径的搜索。每次在 $(a,b)$ 位置会向 $(a+1,b),(a-1,b),(a,b+1),(a,b-1)$ 位置扩展。搜索过程会找到距离 $(x,y)$ 位置**最近**的，且距离不超过 $s-1$ 的**所有**目标位置，或者找不到这样的目标位置。\n\n- 如果存在这样的目标位置，那么在到达目标位置的最短路的方向上，下一时刻会生成一个强度为 $s-1$ 的水方块。\n- 如果不存在这样的目标位置，那么下一时刻，会向 $(x+1,y),(x-1,y),(x,y+1),(x,y-1)$ 位置都生成强度为 $s-1$ 的水方块（如果这个位置可以到达的话）。\n\n请结合图示理解扩散过程。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/9sw2uf0u.png)\n\n如图所示。$S$ 处是平面上该水方块所在的位置。白色的方块是目标位置，打 $\\times$ 的方块是不可经过的位置。我们计算出 $S$ 到达最近的目标位置的最小值 $d_{\\min}=5$，图中标出来的**红色路径**就是三条可能的最短路。\n\n如果 $s>5$，那么下一时刻，在**蓝色箭头**处会有强度为 $s-1$ 的水方块生成。否则，若 $5\\ge s>1$，那么下一时刻除了蓝色箭头外，灰色路径对应的方向**也会生成**强度为 $s-1$ 的水方块。\n\n---\n\n为了检验水流模型的合理性以及其运行效率，莲子提出了这个问题：在 $(x_0,y_0,10^9+1)$ 处，有一个强度为 $k$ 的水方块。询问：在经过充分长的时间后（比如经过了 $10^{9961^{9961}}$ 时刻），有多少个点对 $(a,b)$，满足在 $(a,b,-1)$ 位置，会有水方块生成过。"},{"iden":"input","content":"- 第一行有两个正整数 $n,k$ 和两个整数 $x_0,y_0$，描述实体方块的个数、水方块最大强度，以及初始水方块的位置。\n- 接下来 $n$ 行，每行三个整数 $x_i,y_i,h_i$，描述每个实体方块的位置。保证不存在两个位置完全相同的实体方块。"},{"iden":"output","content":"- 输出共一行一个整数，表示有多少个点对 $(a,b)$，使得充分长时间后 $(a,b,-1)$ 位置有水方块生成过。"},{"iden":"note","content":"### 样例 1 解释\n\n（图片实在太难画啦，将就一下吧。）为了防止方块阻挡导致看不见，方块全部换成了透明的。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/i94wjdgb.png)\n\n初始状态下一根水流柱从高空落下，落在了方块 $(3,4,2)$ 上，进行了扩散。水方块的坐标为 $(3,4,3)$，强度为 $3$。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/e8d9vtl8.png)\n\n- 如图 $3$，根据寻路机制，它会在 $(3,5,3)$ 和 $(4,4,3)$ 上生成强度为 $2$ 的水方块。\n- 如图 $4$，生成的两个支流下方都没有方块，于是在 $(3,5,2)$ 和 $(4,4,2)$ 上生成强度为 $3$ 的水方块。\n- 如图 $5$，水方块 $(3,5,2)$ 下方依旧没有实体方块，于是在 $(3,5,1)$ 生成了强度为 $3$ 的水方块，一直流到 $(3,5,-1)$；水方块 $(4,4,2)$ 下方有实体方块，于是在 $(4,3,2)$ 生成了强度为 $2$ 的水方块。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/g5n7min2.png)\n\n下面只关心水方块 $(4,3,2)$。它下面有实体方块 $(4,3,1)$，于是它向两边扩散，生成强度均为 $1$ 的两个水方块。这两个方块下面都不再有实体方块，于是**一直往下流**到 $(4,2,-1)$ 和 $(5,3,-1)$。\n\n因此，最终一共会有三个位置 $(3,5,-1)$、$(4,2,-1)$、$(5,3,-1)$ 有水方块经过。\n\n### 数据范围及约定\n\n对于所有数据，$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$。"}],"translated_statement":null,"sample_group":[["8 3 3 4\n4 3 1\n4 4 1\n3 3 2\n3 4 2\n4 5 2\n5 4 2\n2 4 3\n4 1 4\n","3\n"],["8 2 3 4\n4 3 1\n4 4 1\n3 3 2\n3 4 2\n4 5 2\n5 4 2\n2 4 3\n4 1 4\n","1"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}