Water Flow Simulation in a 3D Cube Space

In a three‐dimensional space there are n cubes (called entity cubes). Each cube is given by its coordinates \( (x_i, y_i, h_i) \). In this space we simulate a water flow mechanism. In addition to the entity cubes, there will be water cubes. A water cube has an integer strength \( s \) with \( 1\le s\le k \).

Water Flow Rules

1. Vertical Propagation: Suppose at time \( t \) there is a water cube at \( (x,y,h) \) with strength \( s \). If the cell immediately below, \( (x,y,h-1) \), does not contain an entity cube then, at the next time step \( t+1 \), a water cube with full strength \( k \) will appear at \( (x,y,h-1) \). (Note that the new water cube’s strength is always \( k \), regardless of \( s \).)

2. Diffusion (Spread): If at \( (x,y,h) \) there is a water cube of strength \( s>1 \) but \( (x,y,h-1) \) has an entity cube, then the water cube will perform a diffusion operation at height \( h \). When several water cubes are scheduled to be generated at the same position simultaneously, the one with the highest strength takes effect.

Diffusion Details

At height \( h \), the water cube at \( (x,y,h) \) will try to find a path on the two‐dimensional plane (with coordinates \( (x,y) \)). First, a cell \( (a,b) \) on this plane is:

• Passable if there is no entity cube at \( (a,b,h) \); otherwise it is impassable.

• A target if it is passable and the cell below \( (a,b) \) at height \( h-1 \) is also free of entity cubes.

From \( (x,y) \) (which is passable by assumption), perform a breadth‐first search (BFS) on the grid (moves allowed in four directions: up, down, left, right). Let \( d_{min} \) be the minimum distance (if any) from \( (x,y) \) to one or more target positions, with the search limited to radius \( s-1 \) (i.e. paths of length at most \( s-1 \)).

• If one or more target positions are found (that is, \( d_{min} \) exists), then only those initial directions (neighbors of \( (x,y) \)) which lie along a shortest path (i.e. are on some shortest path to a target) will have a water cube of strength \( s-1 \) generated at \( (x',y',h) \) in the next time step.

• If no target position is found within distance \( s-1 \), then in the next time step a water cube of strength \( s-1 \) is generated in every passable neighboring cell \( (x+1,y) \), \( (x-1,y) \), \( (x,y+1) \), \( (x,y-1) \) (if reachable).

Initial Condition and the Question

A water cube with full strength \( k \) is initially placed at \( (x_0, y_0, 10^9+1) \). Once the simulation has run for a very long time (for example, after \( 10^{9961^{9961}} \) time steps), some ground positions (i.e. positions \( (a,b,-1) \)) will have been reached by water at least once. Your task is to determine how many distinct pairs \( (a,b) \) will have received a water cube at the ground level \( h=-1 \) at some moment.

Note: Vertical propagation is instantaneous – if at any column \( (x,y) \) there is a clear vertical path (i.e. no entity cubes block the descent) from the current water cube’s level to \( -1 \), then water will eventually reach the ground at \( (x,y,-1) \) with full strength \( k \) (reset upon vertical drop).

---

All formulas are written in \( \LaTeX \) format.

inputFormat

The input begins with a line containing four integers: n, k, x₀, y₀ (\( 0\le n \le 100 \), \( 1\le k \le 10 \)). Here n is the number of entity cubes, and (\( x_0,y_0,10^9+1 \)) is the initial water cube position with full strength \( k \).

Each of the next n lines contains three integers: x_i, y_i, h_i, specifying that there is an entity cube at position \( (x_i, y_i, h_i) \). It is guaranteed that the positions of the entity cubes are distinct.

All coordinates are in the integer range and the overall area where cubes and water appear is small.

outputFormat

Output a single integer: the number of distinct pairs \( (a,b) \) for which a water cube is generated at \( (a,b,-1) \) at some moment during the simulation.

sample

0 3 0 0

1

</p>