你目前位于代尔夫特（Delft）西北角的酒店，想要前往位于城市东南角的大学竞赛场地。为了到达那里，你必须穿过城市的历史中心。和曼哈顿一样，这座城市由一个 $h \times w$ 的建筑网格组成。但与曼哈顿不同的是，这座城市不仅包含方形的住宅楼，还有一些圆形的中古塔楼。所有的方形建筑均沿坐标轴对齐，边长为 $10\,\text{m}$；所有的圆形塔楼直径均为 $10\,\text{m}$。相邻建筑之间仅有刚好容纳一条宽度可忽略不计的小巷的空间。

代尔夫特水塔。CC BY-SA 3.0，作者 Michiel1972，来自维基百科。

由于你参加比赛已经迟到了，你需要找到从酒店到竞赛场地的最短路径。幸运的是，你有一张城市地图。参见图 D.1 的示例。

图 D.1：样例输入 1 的示意图，红色线条表示一条最短路径。

输入格式

输入包含：

• 一行包含两个整数 $h$ 和 $w$ ($1 \le h, w \le 700$)，表示地图上建筑的行数和列数。
• $h$ 行，每行包含 $w$ 个字符，字符为 ‘O’（表示圆形塔楼）或 ‘X’（表示方形建筑），描述了建筑的形状。

地图的北侧朝上。

输出格式

输出从代尔夫特西北角到东南角的最短路径长度（单位为米）。你的答案允许有最多 $10^{-6}$ 的相对或绝对误差。

样例

输入格式 1

3 5
XOOXO
OXOXO
XXXXO

输出格式 1

71.4159265359

输入格式 2

1 4
XOOX

输出格式 2

45.7079632679