ADOM

A roguelike game draws its world with ASCII characters: every tile is a square, and the map shows the walls of buildings and the hero. We must compute what the hero can see.

The visibility model is realistic: an object hidden behind a wall is not shown, and the hero can only perceive objects within a maximum distance, the visibility radius $r$. In this simplified version the only objects on the map are the square walls of buildings.

Given the map, determine which walls the hero can see.

The first line contains the number of test cases $T$ $(1 \le T \le 100)$.

The first line of each test case contains three integers $n$, $m$, $r$ $(1 \le n, m, r \le 100)$: the height of the board, the width of the board, and the hero's visibility radius.

The next $n$ lines contain $m$ characters each and describe the board: . is an empty tile, X is a wall, and P is the hero's position. Each board contains exactly one P.

For each test case, output the board with every wall (X) that the hero cannot see replaced by .. Print the $T$ boards in order, separating consecutive boards with a single blank line.

Visibility is defined as follows.

• A wall X completely fills its square tile, and there is no gap between two adjacent walls.
• The hero's observation point is exactly the center of the tile containing P.
• A wall is considered visible if there exists a point $Q$ in its square such that (1) the straight-line distance from the observation point to $Q$ is at most $r$, and (2) the open segment from the observation point to $Q$ does not pass through the interior of any other wall. In other words, a wall is visible if even its smallest fragment is visible.
• Because each wall fills its tile completely and adjacent walls leave no gap, a line of sight cannot pass through a point where two walls meet only at a single corner.