Wet Tiles

Alice runs a construction company in Norainia, a town known for its unusually dry weather. It rains only a few days a year there, so many residents put off roof repairs until a leak appears and ruins the floor. Norainia floor tiles look beautiful and hold up badly against water. Once a tile gets wet it is ruined and has to be replaced. Every rainy day brings Alice a flood of calls, and for each house she needs to know how many replacement tiles the crew should bring.

The floor of a house is a grid of square tiles, $X$ tiles wide and $Y$ tiles tall. Water drips from one or more known leak positions above particular tiles. After the first minute, the tile directly under each leak is wet. After every following minute, every dry tile that shares an edge with an already wet tile becomes wet.

Walls stop the water. The house always has four outer walls around the whole grid, so water never leaves it. A house may also have inner walls. Each inner wall covers a connected straight run of tiles and is either axis aligned or set at 45 degrees to both axes. A diagonal wall is a run of tiles that touch only at their corners. Water never enters a tile that holds a wall, and it moves only between tiles that share an edge. Walls may cross each other, and no leak sits over a wall.

Figure 1 shows in gray the damage from three leaks, each marked with a white letter L, over the first five minutes. A tile labeled 2 becomes wet during the second minute, a tile labeled 3 during the third minute, and so on. Black tiles are inner walls that restrict the flow of water. After 5 minutes, 75 tiles are wet.

Figure 1. 75 wet tiles

Given the grid dimensions, the leaks, the inner walls, and the number of minutes $T$ that pass before the crew stops the leaks, count the wet tiles.

Figures 2 through 4 show the second, third, and fourth houses of the first example.

Figure 2. 17 wet tiles

Figure 3. 4 wet tiles

Figure 4. 94 wet tiles

The input describes one or more houses.

Each house begins with a line holding five integers $X$, $Y$, $T$, $L$, $W$. $X$ and $Y$ are the grid dimensions, with $1 \le X \le 1000$ and $1 \le Y \le 1000$. Coordinates are one indexed, so a tile is written as a pair $(x, y)$ with $1 \le x \le X$ and $1 \le y \le Y$. $T$ is the number of minutes that pass before the crew arrives and stops the leaks, with $1 \le T \le 200000$. $L$ is the number of leaks, with $1 \le L \le 100$. $W$ is the number of inner walls, with $0 \le W \le 100$.

The next $2L$ integers, spread over one or more lines, are the $L$ distinct leak positions $(x, y)$.

If $W > 0$, the next $4W$ integers, spread over one or more lines, describe the inner walls. Each wall is given by four integers $x_1$, $y_1$, $x_2$, $y_2$, the coordinates of its two ends. The wall covers every tile on the straight run from $(x_1, y_1)$ to $(x_2, y_2)$. That run is either axis aligned or set at 45 degrees. If the two ends are the same, the wall covers that single tile.

A line holding the single integer -1 ends the input.

For each house, print the number of tiles that are wet after $T$ minutes, one per line, in the order the houses appear in the input.