Background

Lianzi designed a 3D space software. This software can simulate a real physics engine, including solid blocks and flowing water blocks. However, computing a large amount of water flow at the same time will put a heavy load on the software.

So, Lianzi hopes to find an algorithm that can quickly compute the result after these water flow simulations.

Problem Description

The water flow model designed by Lianzi is as follows:

Consider a 3D space. There are $n$ cubes in this space. We use coordinates $(x_i,y_i,h_i)$ to describe the position of each cube. These cubes are called solid blocks.

Now we will simulate a water flow mechanism in this space. Specifically, we define water blocks. A water block has an intensity $s$, with range $[1,k]$.

Simulation Rules

• Suppose there is a water block with intensity $s$ at $(x,y,h)$, and there is no solid block at $(x,y,h-1)$. Then at the next moment, a water block with intensity $k$ will be generated at $(x,y,h-1)$. Note: no matter what the current value of $s$ is, the water block generated at $(x,y,h-1)$ always has intensity $k$.
• Suppose there is a water block with intensity $s$ at $(x,y,h)$, and $s>1$, and there is a solid block at $(x,y,h-1)$. Then a diffusion operation will be performed.
• If at the next moment, multiple water blocks would be generated at the same position $(x,y,h)$, then the intensity of the final generated water block is the maximum intensity among them.

Diffusion Operation

Since the diffusion operation is abstract, it is recommended to understand it together with the diagrams.

For a water block at $(x,y,h)$, it will perform pathfinding on the plane at height $h$. To describe this process, consider the plane at height $h$:

• If there is a solid block at $(x,y,h)$ in space, then on the plane, the cell $(x,y)$ is not passable. Otherwise, if there is no solid block, then $(x,y)$ is passable.
• When $(x,y)$ is passable, if there is no solid block at $(x,y,h-1)$ in space, then on the plane, the cell $(x,y)$ is called a target position. There can be more than one target position.

From the diffusion preconditions, we know that on the plane the cell $(x,y)$ is passable, but it is not a target position.

Starting from $(x,y)$ on the plane, perform a path search. Each step expands from $(a,b)$ to $(a+1,b),(a-1,b),(a,b+1),(a,b-1)$. The search will find all target positions whose distance to $(x,y)$ is the minimum, and that minimum distance is at most $s-1$, or it may find no such target position.

• If such target positions exist, then at the next moment, in the direction of the shortest paths to those target positions, water blocks with intensity $s-1$ will be generated.
• If no such target position exists, then at the next moment, water blocks with intensity $s-1$ will be generated at all of $(x+1,y),(x-1,y),(x,y+1),(x,y-1)$ (if those positions are reachable).

Please refer to the diagrams to understand the diffusion process.

As shown in the figure, $S$ is the position of this water block on the plane. The white blocks are target positions, and the blocks marked with $\times$ are not passable. We compute the minimum distance from $S$ to the nearest target position as $d_{\min}=5$. The red paths marked in the figure are three possible shortest paths.

If $s>5$, then at the next moment, water blocks with intensity $s-1$ will be generated at the positions indicated by the blue arrows. Otherwise, if $5\ge s>1$, then at the next moment, besides the blue arrows, the directions corresponding to the gray paths will also generate water blocks with intensity $s-1$.

To verify whether the water flow model is reasonable and efficient, Lianzi raises the following question: At $(x_0,y_0,10^9+1)$, there is a water block with intensity $k$. The question is: after a sufficiently long time (for example, after $10^{9961^{9961}}$ moments), how many pairs of points $(a,b)$ satisfy that at position $(a,b,-1)$, a water block has ever been generated.

Input Format

• The first line contains two positive integers $n,k$ and two integers $x_0,y_0$, describing the number of solid blocks, the maximum intensity of water blocks, and the position of the initial water block.
• The next $n$ lines each contain three integers $x_i,y_i,h_i$, describing the position of each solid block. It is guaranteed that no two solid blocks share the exact same position.

Output Format

• Output one integer in a single line, indicating how many pairs $(a,b)$ have had a water block generated at $(a,b,-1)$ after a sufficiently long time.

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

Hint

Sample 1 Explanation

(The picture is really too hard to draw, so please bear with it.) To prevent blocks from blocking the view, all blocks are replaced with transparent ones.

In the initial state, a column of water falls from a high altitude and lands on the block $(3,4,2)$, then it diffuses. The water block is at $(3,4,3)$ with intensity $3$.

• As in Figure 3, according to the pathfinding mechanism, it generates water blocks with intensity $2$ at $(3,5,3)$ and $(4,4,3)$.
• As in Figure 4, there are no blocks below both generated branches, so water blocks with intensity $3$ are generated at $(3,5,2)$ and $(4,4,2)$.
• As in Figure 5, there is still no solid block below the water block $(3,5,2)$, so it generates a water block with intensity $3$ at $(3,5,1)$, and it keeps flowing down to $(3,5,-1)$; the water block $(4,4,2)$ has a solid block below it, so it generates a water block with intensity $2$ at $(4,3,2)$.

Now we only focus on the water block $(4,3,2)$. There is a solid block $(4,3,1)$ below it, so it diffuses to both sides, generating two water blocks both with intensity $1$. Below these two blocks there are no more solid blocks, so they keep flowing downward to $(4,2,-1)$ and $(5,3,-1)$.

Therefore, in the end, there will be water blocks passing through three positions: $(3,5,-1)$, $(4,2,-1)$, and $(5,3,-1)$.

Constraints and Notes

For all testdata, $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 by ChatGPT 5