题目描述

Hansel 和 Gretel 在玩一个著名的游戏 "Arrows"，游戏在一个 $\text{R}$ 行 $\text{S}$ 列的棋盘上进行。在棋盘的每一个方格上，都有一个箭头指向东西南北四个方向。

Hansel 先手，他进行的操作是给刚好 $k$ 个方格染色，但不能染最后一列的。然后轮到 Gretel，他会将一个机器人放在棋盘第一列的任意方格中。机器人会按照方格上指的方向移动一格，当它到达了最后一列中的任意方格，机器人会停下，游戏就结束了。

游戏的输赢由以下规则决定：

• 如果机器人停下来，游戏结束，并满足机器人经过的路径中只有一个方格被染色，那么 Hansel 获胜。否则若机器人经过的路径中没有或多于一个方格被染色，那么 Gretel 获胜。
• 如果机器人陷入了死循环，那么 Hansel 获胜。

机器人经过的方格包括：起始方格，游戏中穿过的方格，以及游戏结束时停留在的方格。数据保证：Gretel 不存在任意一种放置方法使得机器人走出棋盘。

如果 Hansel 无法必胜，请输出 -1，否则请输出以任意顺序输出任意一种满足条件染色方案，即输出 $\text{k}$ 个被染色的方格的坐标。

输入格式

第一行包含 $3$ 个整数 $\text{R}$，$\text{S}$，$\text{K}$。

接下来 $\text{R}$ 行，每行包含一个长度为 $\text{S}$ 的字符串，其中只包含 L（左），R（右），U（上），D（下） 四种代表方向的字符。

输出格式

如果 Hansel 无法必胜，输出 -1。

否则，输出 $\text{K}$ 行。每行包含两个用空格隔开的整数 $\text{A}$ 和 $\text{B}$（$1\le \text{A}\le \text{R}$，$1\le \text{B}\le \text{S}$）表示被 Hansel 染色的方格的坐标 $(\text{A},\text{B})$。所有被染色的方格必须互不相同。

本题使用 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

样例说明

样例一解释

如果 Hansel 将 $(4,2)$ 染色，机器人无论如何都会经过该点，因此 Hansel 必胜。

样例二解释

由于 Hansel 必须将两个方格染色，说明至少有一行不会有方格被染色。Gretel 可以把机器人放在那一行，从而经过 0 次被染色的方格，从而 Gretel 获胜。

样例三解释

请观察题面中的图片。

数据规模与约定

对于 $100\%$ 的数据，$1\le \text{R}\times \text{S}\le 10^6$，$1\le \text{K}\le 50$。

题目来源

题目译自 COCI2016-2017 Contest#5 T6 Strelice。

Translated & Checker By cyl06。未经作者许可，禁止搬运题面和 checker。