瓦西里·彼得罗维奇(Vasily Petrovich)拥有的商店的地下室里已经繁殖了数百只老鼠。瓦西里·彼得罗维奇可能没有注意到他们的存在,但他们养成了潜入仓库并从那里偷食物的习惯。瓦西里·彼得罗维奇再也无法忍受了,他必须消灭地下室里的老鼠。由于捕鼠器已经过时,起不到什么作用,而老鼠药不仅会毒死老鼠,还会毒死不专心的人,所以他选择了一个激进的办法:在地下室炸掉两枚手榴弹(他没有更多的了)。
在这个问题中,我们将商店地下室呈现为一个由 n × m 单元组成的矩形表格。一些牢房被墙壁占据,其余的则是空的。瓦西里一直在观察老鼠,他发现它们在特定的时间睡觉,而且一直睡在同一个地方。他想在这个方便的时候引爆一枚手榴弹。在地下室的平面图上,他在牢房里标出了熟睡的老鼠。当然,这些细胞没有被墙壁占据。
手榴弹只能在未被墙壁占据的牢房中爆炸。手榴弹的爆炸波分布如下。我们假设手榴弹爆炸发生在时间 0。在这个初始时间内,只有手榴弹爆炸的单元格才会“清除”。如果在时间 t 某个单元格被清除,那么在时间 t + 1 那些未被墙壁占据的侧面相邻单元格也会被清除(其中一些单元格之前可能已经被清除)。冲击波持续了 d 秒,然后立即消失。
爆炸波分布示例:图1为爆炸前的情况,下图为时间0、1、2、3、4的“清晰”单元格。因此,图中爆炸波分布时间为d=4秒。
瓦西里彼得罗维奇想知道,他是否可以选择两个单元来爆炸手榴弹,从而清除所有睡着的老鼠的单元。编写程序找出它。
输入
第一行包含三个整数 n、m 和 d,用单个空格分隔(4 ≤ n、m ≤ 1000、1 ≤ d ≤ 8)。接下来的 n 行包含表示地下室平面图的表格。表的每一行由 m 个字符组成。字符“X”表示对应的单元格被墙占据,字符“.”。代表一个空单元格,字符“R”代表一个有睡眠老鼠的空单元格。
保证第一行和最后一行以及第一列和最后一列由字符“X”组成。该计划至少有两个空单元格。至少有一间牢房里有熟睡的老鼠。
输出
如果不可能用熟睡的老鼠炸毁所有单元格,则打印一个整数 -1。否则,打印四个空格分隔的整数 r1, c1, r2, c2,这意味着一枚手榴弹应该在单元格 (r1, c1) 中爆炸,而另一枚则在单元格 (r2, c2) 中爆炸。
考虑表行从上到下编号为 1 到 n 和表列 — 从左到右编号为 1 到 m。由于r1和r2代表表中的行号,c1和c2代表表中的列号,因此它们应该满足以下限制:1≤r1,r2≤n,1≤c1,c2≤m。禁止在同一牢房内两次吹手榴弹。手榴弹的爆炸波可以交叉。有可能一颗手榴弹爆炸没有消灭任何老鼠,而另一颗则消灭了所有老鼠。
示例
输入 #1
4 4 1 XXXX XR.X X.RX XXXX
输出 #1
2 2 2 3
输入 #2
9 14 5 XXXXXXXXXXXXXX X....R...R...X X..R.........X X....RXR..R..X X..R...X.....X XR.R...X.....X X....XXR.....X X....R..R.R..X XXXXXXXXXXXXXX
输出 #2
2 3 6 9
输入 #3
7 7 1 XXXXXXX X.R.R.X X.....X X..X..X X..R..X X....RX XXXXXXX
输出 #3
-1