题目描述

Hansel 和 Gretel 正在玩「箭头游戏」。

该游戏在一个 $R$ 行 $S$ 列的棋盘上进行。其中每一个棋格内有一个箭头（$\leftarrow$、$\rightarrow$、$\uparrow$、$\downarrow$ 之一）。

游戏开始后，Hansel 可以选择任意 $K$ 个不位于最后一列的棋格进行填涂。接着，Gretel 可以选择第一列的任意一个棋格，作为机器人的初始棋格。机器人在放置到初始棋格后将按照箭头的指示自动行走。机器人一旦走到了最后一列，它将立即停止行走。

判定输赢的方式如下：

• 如果机器人在有限的时间内停在了最后一列，那么：当且仅当机器人恰好经过一个有色棋格时，判定 Hansel 获胜，否则 Gretel 获胜。
• 如果机器人无法停止行走（即处于无限循环的状态），那么判定 Hansel 获胜。

规定机器人经过的棋格包括初始棋格、终止棋格以及路径上的其它所有棋格。同时，数据保证箭头不会指向棋盘外部。

你的任务是判断 Hansel 是否有必胜的方案（即对于 Gretel 所选择的任意一个合法的初始棋格，Hansel 的填涂方案都可以使自己获胜）。如果有必胜的方案，输出该方案；否则输出 $-1$。

输入格式

第一行，三个整数 $R,S,K$。

接下来的 $R$ 行，每行 $S$ 个字符 $\texttt L$、$\texttt U$、$\texttt R$ 或 $\texttt D$，分别表示对应棋格内的箭头为 $\leftarrow$、$\rightarrow$、$\uparrow$ 和 $\downarrow$。

输出格式

如果没有必胜的方案，输出 $-1$。

否则输出 $K$ 行，每行两个整数 $A,B$，表示选择的 $K$ 个将要涂色的棋格。棋格必须互不相同。如果存在多种方案，请输出任意一种。

Special Judge 对输出格式要求较严，因此请勿在每行行尾添加多余空格。

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

提示

【样例 1 解释】

填涂 $(4,2)$ 后，无论初始棋格位于第一列的哪里，机器人都会经过 $(4,2)$。

【样例 2 解释】

由于需要填涂 $2$ 个棋格，因此至少有一行没有有色棋格。只要 Gretel 选择没有有色棋格的那一行的第一列放置机器人，Gretel 就会获胜。

【样例 3 图解】

【数据规模与约定】

对于 $100\%$ 的数据，$1 \le R \times S \le 10^6$，$1 \le K \le 50$，$1 \le A \le R$，$1 \le B \lt S$。

【提示与说明】

欢迎大家通过私信或发帖对自行编写的 Special Judge 进行 hack。

题目译自 COCI 2016-2017 CONTEST #5 T6 Strelice。

本题分值按 COCI 原题设置，满分 $160$。