Problem Description

Hansel and Gretel are playing the "arrow game".

The game is played on a board with $R$ rows and $S$ columns. Each cell contains an arrow (one of $\leftarrow$, $\rightarrow$, $\uparrow$, $\downarrow$).

After the game starts, Hansel may choose any $K$ cells that are not in the last column to color. Then, Gretel may choose any cell in the first column as the robot's starting cell. After the robot is placed in the starting cell, it will move automatically following the direction of the arrows. Once the robot reaches the last column, it stops immediately.

The winner is decided as follows:

• If the robot stops in the last column in finite time, then: Hansel wins if and only if the robot passes through exactly one colored cell; otherwise Gretel wins.
• If the robot cannot stop (i.e. it is in an infinite loop), then Hansel wins.

The cells the robot passes through include the starting cell, the ending cell, and all other cells along the path. The testdata guarantees that no arrow points outside the board.

Your task is to determine whether Hansel has a winning strategy (that is, for any valid starting cell chosen by Gretel, Hansel's coloring plan can make him win). If there is a winning strategy, output such a plan; otherwise output $-1$.

Input Format

The first line contains three integers $R, S, K$.

The next $R$ lines each contain $S$ characters, each being \texttt L, \texttt R, \texttt U, or \texttt D, meaning the arrow in that cell is $\leftarrow$, $\rightarrow$, $\uparrow$, and $\downarrow$, respectively.

Output Format

If there is no winning strategy, output $-1$.

Otherwise, output $K$ lines. Each line contains two integers $A, B$, meaning one of the $K$ cells to be colored. All chosen cells must be distinct. If multiple solutions exist, output any one of them.

The Special Judge is quite strict about the output format, so do not add extra spaces at the end of any line.

4 3 1
DRD
DUD
DUD
RUL

4 2

3 3 2
RRR
RRR
RRR

-1

4 4 2
RRDL
RRDL
DLRD
RRRL

2 3
4 1

Hint

[Sample 1 Explanation]

After coloring $(4,2)$, no matter where the starting cell is in the first column, the robot will pass through $(4,2)$.

[Sample 2 Explanation]

Because you need to color $2$ cells, at least one row will have no colored cells. As long as Gretel chooses the cell in the first column of that row as the robot's starting position, Gretel will win.

[Sample 3 Illustration]

[Constraints]

For $100\%$ of the data, $1 \le R \times S \le 10^6$, $1 \le K \le 50$, $1 \le A \le R$, $1 \le B \lt S$.

[Hints and Notes]

Everyone is welcome to hack the self-written Special Judge by private message or by posting.

This problem is translated from COCI 2016-2017 CONTEST #5 T6 Strelice.

The score of this problem follows the original COCI setting, with a full score of $160$.

Translated by ChatGPT 5