Problem J
Connect-N

A popular connection game that is well-known around the world is Connect Four. In this two-person game, each player is assigned a colored disc (red or blue) and takes turns dropping one of their colored discs from the top into a seven-column, six-row vertically upright game board. The disc will go into the lowest free row of that column. The objective of the game is to be the first player to form four discs in a horizontal, vertical, or diagonal line. The below diagrams show examples of ways for a player to win:

In this problem, you will not implement the Connect Four game in its entirety. However, you will be writing a program that checks whether there is currently a win on the board. Additionally, there are two modifications to the game:

• The game is no longer Connect Four but rather Connect-$N$, where $N$ is the number of discs a player needs to form a winning horizontal, vertical, or diagonal line.

• The board has dimensions $(X,Y)$, where $X$ is the number of rows and $Y$ is the number of columns. Thus, the game board is no longer a static $(6,7)$ grid.

You will be given the specification of a Connect-$N$ board and the location of all the colored discs on the board. Based on this information, you will need to determine whether the red player, blue player, or no player has a Connect-$N$ on the board.

Input

The input contains the specification of a single Connect-$N$ board. The specification starts with a line with three non-zero positive integers, $X$, $Y$, and $N$ that specify the dimensions of the board and the connection amount ($X$, $Y$, and $N$ are described in the problem description above). This is followed by $X$ lines, each corresponding to a line of the board. Each of these lines has $Y$ characters, each separated from the next by a single space, corresponding to each column of that row. A R denotes that there is a red disc in that position, a B denotes that there is a blue disc in that position, while a O denotes that there is no disc in that position.

You can assume the following:

• Possible values for the dimensions of the board range from $2$ to $100$ (i.e., $2 \leqslant X \leqslant 100$ and $2 \leqslant Y \leqslant 100$).

• $N$ will always be less than or equal to the board dimensions (i.e., $N\leqslant X$, and $ N\leqslant Y$).

• For a given board, if there is a winner on the board then it is either red or blue and not both.

Output

The output contains a single line denoting if there is a winner on the board. If the red player has a Connect-$N$ then print RED WINS. If the blue player has a Connect-$N$ then print BLUE WINS. If the board has no winner (i.e., no player has a Connect-$N$) then print NONE.

3 6 3
B O O O O O
B O O O O O
B R R O O O

BLUE WINS

4 4 4
O O O O
O O O O
B B B O
R R R R

RED WINS

2 3 2
O O O
R B O

NONE