CF254D.Rats

Rats have bred to hundreds and hundreds in the basement of the store, owned by Vasily Petrovich. Vasily Petrovich may have not noticed their presence, but they got into the habit of sneaking into the warehouse and stealing food from there. Vasily Petrovich cannot put up with it anymore, he has to destroy the rats in the basement. Since mousetraps are outdated and do not help, and rat poison can poison inattentive people as well as rats, he chose a radical way: to blow up two grenades in the basement (he does not have more).

In this problem, we will present the shop basement as a rectangular table of n × m cells. Some of the cells are occupied by walls, and the rest of them are empty. Vasily has been watching the rats and he found out that at a certain time they go to sleep, and all the time they sleep in the same places. He wants to blow up a grenade when this convenient time comes. On the plan of his basement, he marked cells with sleeping rats in them. Naturally, these cells are not occupied by walls.

Grenades can only blow up in a cell that is not occupied by a wall. The blast wave from a grenade distributes as follows. We assume that the grenade blast occurs at time 0. During this initial time only the cell where the grenade blew up gets 'clear'. If at time t some cell is clear, then at time t + 1 those side-neighbouring cells which are not occupied by the walls get clear too (some of them could have been cleared before). The blast wave distributes for exactly d seconds, then it dies immediately.

An example of a distributing blast wave: Picture 1 shows the situation before the blast, and the following pictures show "clear" cells by time 0,1,2,3 and 4. Thus, the blast wave on the picture distributes for d = 4 seconds.

Vasily Petrovich wonders, whether he can choose two cells to blast the grenades so as to clear all cells with sleeping rats. Write the program that finds it out.

瓦西里·彼得罗维奇所经营的商店地下室中，老鼠已经繁衍到了成百上千只。瓦西里·彼得罗维奇或许尚未察觉它们的存在，但这些老鼠却已养成习惯，偷偷溜进仓库偷取食物。瓦西里·彼得罗维奇再也无法容忍，他必须消灭地下室里的老鼠。由于捕鼠夹早已过时且毫无效果，而老鼠药又可能在毒杀老鼠的同时误伤粗心的人，他选择了一种激进的方式：在地下室中引爆两枚手榴弹（他仅有这两枚）。

本题中，我们将商店地下室建模为一个 $n \times m$ 的矩形网格。其中部分格子被墙壁占据，其余格子为空。瓦西里一直观察老鼠的活动规律，并发现它们会在某个特定时刻入睡，且始终在相同的位置睡觉。他打算就在这个“方便的时刻”引爆手榴弹。他在地下室平面图上标出了所有有老鼠睡觉的格子。显然，这些格子均不被墙壁占据。

手榴弹只能在非墙壁格子中引爆。手榴弹爆炸产生的冲击波按如下方式传播：我们假设手榴弹在时刻 $0$ 爆炸；此时，仅爆炸所在的格子被“清空”。若在时刻 $t$ 某格子已被清空，则在时刻 $t+1$，该格子所有与之共边相邻（即上下左右四个方向）且不被墙壁占据的格子也将被清空（其中一些格子可能已在更早时刻被清空）。冲击波持续传播恰好 $d$ 秒，之后立即消失。

冲击波传播过程示例：图1显示爆炸前的状态，后续各图分别显示时刻 $0,1,2,3,4$ 时已被“清空”的格子。因此，图中所示冲击波传播持续时间为 $d = 4$ 秒。

瓦西里·彼得罗维奇想知道：能否选择两个格子来引爆手榴弹，使得所有有老鼠睡觉的格子均被清空？请编写程序解决这一问题。

The first line contains three integers n, m and d, separated by single spaces (4 ≤ n, m ≤ 1000, 1 ≤ d ≤ 8). Next n lines contain the table that represents the basement plan. Each row of the table consists of m characters. Character "X" means that the corresponding cell is occupied by the wall, character "." represents a empty cell, character "R" represents a empty cell with sleeping rats.

It is guaranteed that the first and the last row, as well as the first and the last column consist of characters "X". The plan has at least two empty cells. There is at least one cell with sleeping rats.

第一行包含三个整数 $n$、$m$ 和 $d$，以单个空格分隔（$4 \leq n, m \leq 1000$，$1 \leq d \leq 8$）。接下来的 $n$ 行描述了地下室的平面图。每行包含 $m$ 个字符：字符 "X" 表示该单元格被墙壁占据；字符 "." 表示空单元格；字符 "R" 表示一个有熟睡老鼠的空单元格。

保证第一行与最后一行、第一列与最后一列均由字符 "X" 组成。该平面图至少包含两个空单元格，且至少存在一个带有熟睡老鼠的单元格。

If it is impossible to blow up all cells with sleeping rats, print a single integer -1. Otherwise, print four space-separated integers _r_1, _c_1, _r_2, _c_2, that mean that one grenade should go off in cell (_r_1, _c_1), and the other one — in cell (_r_2, _c_2).

Consider the table rows numbered from top to bottom from 1 to n and the table columns — from left to right from 1 to m. As _r_1 and _r_2 represent the row numbers, and _c_1 and _c_2 represent the column numbers in the table, they should fit the limits: 1 ≤ _r_1, _r_2 ≤ n, 1 ≤ _c_1, _c_2 ≤ m. It is forbidden to blow a grenade twice in the same cell. The blast waves of the grenades can intersect. It is possible that one grenade blast destroys no rats, and the other one destroys all of them.

如果无法用两枚手榴弹炸毁所有沉睡的老鼠，则输出单个整数 $-1$。否则，输出四个以空格分隔的整数 $r_1,\ c_1,\ r_2,\ c_2$，表示一枚手榴弹应在单元格 $(r_1,\ c_1)$ 爆炸，另一枚应在单元格 $(r_2,\ c_2)$ 爆炸。

表格的行从上到下编号为 $1$ 到 $n$，列从左到右编号为 $1$ 到 $m$。由于 $r_1$ 和 $r_2$ 表示表格中的行号，$c_1$ 和 $c_2$ 表示列号，因此它们必须满足如下限制：$1\le r_1,\ r_2\le n$，$1\le c_1,\ c_2\le m$。禁止在同一个单元格中引爆两枚手榴弹。两枚手榴弹的冲击波可以相交。有可能其中一枚手榴弹未消灭任何老鼠，而另一枚消灭了全部老鼠。