In gym class, you are playing football on an $N$ by $M$ grid. Everyone in the class is put into one of two teams, $A$ and $B$. Team $A$ is trying to score towards the right (towards column $M$), while Team $B$ is trying to score to the left (towards column $1$).

You know the positions of all the players on the field, but not who has the ball. The person with the ball will always try to score a field goal. It will be blocked if there is a member of the opposite team within $K$ units directly in front of them (assume all the players are facing the direction they are scoring).

You want to consider every possible scenario. Hence, for each player, assuming they have the ball, will they score or will they be blocked?

Constraints

$1\le N\times M\le {10}^5$

$1\le K\le M$

Subtask 1 [25%]

$1\le N\times M\le {10}^3$

Subtask 2 [75%]

No additional constraints.

Input Specification

The first line of input contains three integers $N$, $M$, and $K$, representing the dimensions of the grid, and the distance required to block a field goal.

The next $N$ lines of input each contain $M$ characters. If the $c$-th character on the $r$-th row is an A or B, there is a player on that team at that position. Otherwise, the character will be a ., which indicates an empty position.

Output Specification

Output an $N$ by $M$ grid where each position is represented by a . indicating an empty position, a Y meaning the player would score their field goal, or an N meaning the player would be blocked.

Sample Input

2 5 2
A.B.A
.BB..

Sample Output

N.N.Y
.YY..

Explanation for Sample

In the first row, the player at $(1,1)$ from Team A is blocked by a Team B player at $(1,3)$. The player at $(1,3)$ from Team B is blocked by a Team A player at $(1,1)$. The player at $(1,5)$ from Team A has no blockers and thus scores.

In the second row, both players at $(2,2)$ and $(2,3)$ from Team B have no blockers from team A within the specified distance and can score.