C. Queen Bee Last Stand Off (Brown)
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

High above the track, contestants face off on a massive $$$n \times m$$$ grid.

The Queen likes Yellow and Black because they are her colors.

Queen Bee.

The grid is initially filled with ('.'). Then, a sequence of moves is played, with each move consisting of painting a cell either Black ('B') or Yellow ('Y'). Each day, two bees compete against each other in a tough match on the grid, where one bee paints cells Yellow and the other paints cells Black.

The game is simple: they fight 1v1, and the winner earns the right to choose any empty cell and paint it with his color.

The tension is great—the first bee to achieve a line of at least $$$k$$$ connected pieces of their color, horizontally, vertically, or diagonally, will not only earn Queen Bee's respect but also the legendary Queen Honey Pot as a prize and victory!

However, due to the intensity of the competition, they forgot about the $$$k$$$-connected-pieces rule, and eventually, they ended up coloring the entire grid (they played exactly $$$n \times m$$$ moves).

Now, they want to iterate through the moves again to determine the actual winner.

Given $$$n$$$, $$$m$$$, $$$k$$$, and the sequence of moves, determine which bee achieves a line of length at least $$$k$$$ first. If neither achieves this, the game results in a draw.

Input

The first line contains three space integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \le n, m \le 1000$$$, $$$1 \le k \le \min(n, m)$$$) — denotes the number of rows, is the number of columns, and the number of connected cells of the same color (Black or Yellow) required, respectively.

The next $$$n \cdot m$$$ lines represent the sequence of moves, the $$$i_{th}$$$ line contains three integers $$$p \in$$$ ('B', 'Y') which represents the color of bee that won the $$$i_{th}$$$ move, $$$x$$$ ($$$1 \le x \le n$$$), and $$$y$$$ ($$$1 \le y \le m$$$) — $$$x$$$, $$$y$$$ are the coordinates of the cell respectively.

Output

Print one of the following characters:

  • B if Black has a winning connection of length $$$k$$$.
  • Y if Yellow has a winning connection of length $$$k$$$.
  • N if neither Black nor Yellow has a winning connection of length $$$k$$$ in the given state.
Example
Input
3 3 3
B 1 1
Y 2 1
B 1 2
Y 2 2
B 1 3
Y 3 1
Y 3 2
Y 3 3
Y 2 3
Output
B