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 on the board contains an arrow ($\leftarrow$, $\rightarrow$, $\uparrow$, $\downarrow$).

At the start of the game, Hansel can choose any $K$ cells that are not in the last column to paint. Then, Gretel can choose any cell in the first column as the initial cell for the robot. The robot, once placed in the initial cell, will move automatically according to the arrows. The robot will stop immediately once it reaches the last column.

The rules for determining the winner are as follows:

• If the robot stops within a finite time in the last column, then Hansel wins if and only if the robot has passed exactly one painted cell; otherwise, Gretel wins.
• If the robot cannot stop (i.e., it is in an infinite loop), then Hansel wins.

The cells passed by the robot include the initial cell, the terminal cell, and all other cells on the path. Additionally, the arrows are guaranteed not to point outside the board.

Your task is to determine if Hansel has a winning strategy (i.e., for any valid initial cell chosen by Gretel, Hansel's painting strategy ensures his victory). If there is a winning strategy, output the strategy; otherwise, output $-1$.

Input Format

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

The next $R$ lines each contain $S$ characters $\texttt{L}$, $\texttt{U}$, $\texttt{R}$, or $\texttt{D}$, representing the arrows in the cells as $\leftarrow$, $\rightarrow$, $\uparrow$, and $\downarrow$ respectively.

Output Format

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

Otherwise, output $K$ lines, each containing two integers $A$ and $B$, representing the $K$ cells to be painted. The cells must be distinct. If there are multiple solutions, output any one of them.

Note: Do not add extra spaces at the end of each line.

Sample Input and Output

Sample Input #1

4 3 1
DRD
DUD
DUD
RUL

Sample Output #1

4 2

Sample Input #2

3 3 2
RRR
RRR
RRR

Sample Output #2

-1

Sample Input #3

4 4 2
RRDL
RRDL
DLRD
RRRL

Sample Output #3

2 3
4 1

Notes

[Explanation of Sample 1]

After painting $(4,2)$, regardless of where the initial cell in the first column is, the robot will pass through $(4,2)$.

[Explanation of Sample 2]

Since 2 cells need to be painted, there will be at least one row without a painted cell. If Gretel places the robot in the first column of that row, she will win.

[Diagram for Sample 3]

[Data Range]

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 < S$.

[Hint and Disclaimer]

Feel free to hack the custom Special Judge via private message or forum post.

Translated from COCI 2016-2017 CONTEST #5 T6 Strelice.

This problem is scored according to the original COCI settings, with a maximum score of $160$.

见题面 Input 部分

见题面 Output 部分