题目描述

我是谁？我是什么？我为什么是我？这些都是十分困难的问题，在过去的几千年里这些问题让哲学家们可靠地忙碌着。但是当提到「我在哪儿？」的时候，现代智能手机和 GPS 卫星在很大程度上把人们研究这个问题的兴趣带走了。

为了给最近失业的思考「我在哪儿？」的空间哲学家们再泼盆冷水，即时制图定位公司（Instant Cartographic Positioning Company, ICPC）决定进行一次演示，说明 GPS 比老式地图强大得多。他们的论点是，只有当你已经知道你在哪儿的时候，地图才是有用的，但如果你从一个未知的地方开始，地图就不那么有用了。

在这次演示中，ICPC 创建了一个测试区，它被设置成一个无界的笛卡尔坐标网格。大多数单元格是空的，但一些单元中有一个标记（见图 L.1(a) 有五个标记单元格的例子）。所有空的单元格看起来都一样，所有有标记的单元格看起来也一样。假设你得到了一张测试区的地图（即所有标记的位置），你被安排在一个（你不知道的）单元格中。你要花多长时间才能确定你实际所在的位置？ICPC 的答案很明确：有可能是非常、非常长的时间，而 GPS 会立即给你答案。但具体要多长时间呢？

在试验中，测试对象将沿着一个不断扩大的顺时针螺旋轨迹探索它所处的环境，其最初的几步如图 L.1(b) 所示。开始的单元格被标记为 $0$，数字表示其他单元格被访问的顺序。测试对象只有在单元格上才能看到在其中的标记，一旦它根据目前所看到的单元格确定了自己的位置，它就会停止探索。这意味着，观察到的空的和有标记的网格单元的序列只可能从一个可能的起始位置开始。网格是无界的，但探索步骤将是有限的，因为一旦测试对象看到了网格上的所有标记，它肯定会知道自己在哪里。

让数以百计的测试对象绕着圈子跑可能会很昂贵，所以 ICPC 认为编写模拟程序会更便宜更快。你能帮帮他们吗？

输入格式

输入描述了一个网格。第一行两个整数 $d_x,d_y\ (1\le d_x,d_y\le 100)$。接下来 $d_y$ 行，每行 $d_x$ 个字符，这部分描述这个测试网格。第 $j$ 行第 $i$ 个字符表示坐标为 $(i,d_y-j+1)$ 的单元格的内容。字符是 . 和 X 之一，分别表示单元格空或被标记。

被标记的单元格总数在 $1$ 和 $100$ 之间（包括两端）。所有在输入描述范围之外的单元格都是空的。

输出格式

在 ICPC 的实验中，测试对象知道它会从某个满足 $1\le x\le d_x,1\le y\le d_y$ 的位置 $(x,y)$ 出发。

输出三行。第一行包含一个实数，表示假设起点是均匀随机选取的，为了确定起始位置而需要游走的期望步数。这个实数与答案之间的绝对误差不能超过 $10^{-3}$。

第二行输出测试对象为了确定起始位置而需要游走的最大步数。

第三行输出所有达到了这个最大步数的起始位置 $(x,y)$。坐标按 $y$ 递增的顺序输出，然后（如果 $y$ 坐标相同）按 $x$ 坐标递增的顺序输出。

5 5
....X
.X...
.....
X..X.
..X..

9.960
18
(1,4) (4,5)

5 1
..XX.

4.600
7
(1,1) (5,1)