Joe 和 Marty 发明了一个新游戏。这个游戏叫做“拯救绵羊”，它是在一个矩形网格上进行的。首先，Joe 沿着网格线画了一个矩形，然后在矩形内填充了一些方格（并非全部），这些方格代表绵羊。接着，Marty 在矩形内剩余的方格中选择一个填充为黑色，该方格代表狼。随后，他们两人分别努力实现游戏目标，即在绵羊周围画出尽可能短的围栏，使得狼无法接触到它们。
具体来说，围栏必须沿着网格线绘制，并且必须将网格划分为两个区域。所有的绵羊都应位于围栏所包围的区域内，而狼则应留在围栏外的区域。围栏必须位于所选的矩形内，它可以部分沿着矩形的边界延伸。
赢得游戏的人是画出最短围栏的那个人。有时，无法画出所需的围栏，在这种情况下，双方都输掉游戏。你的任务是编写一个程序，在可能的情况下赢得游戏。
输入格式
输入包含多组测试数据。每组数据的第一行包含两个由空格分隔的整数 $M, N$ ($1 \le M, N \le 1000$)，分别代表矩形的高度和宽度。
接下来有 $M$ 行，代表矩形的内容。每一行指定矩形的一行，包含一个长度为 $N$ 的字符串。字符串中的每个字符代表一个网格方格，它可以是大写字母“X”、大写字母“O”或符号“.”（点）。字母“X”代表狼，字母“O”代表绵羊，点“.”代表网格中未被占用的方格。每种动物在网格中恰好占据一个方格，且矩形中恰好有一只狼和至少一只绵羊。
输出格式
对于每组测试数据，输出一行，包含一个整数，表示根据游戏规则将绵羊与狼隔开的最短围栏长度。假设网格中每个方格的边长为单位长度。如果无法画出围栏，则输出“-1”。
样例
样例输入 1
5 5 ..... ..OOO ..OXO O...O ..OOO 3 5 ..O.. .OXO. ..O.. 2 3 .O. OXO 1 3 OXO
样例输出 1
26 -1 12 -1
说明
由于一个错误的假设，原始题目描述（2016年 CTU Open Contest 中使用的版本）要求围栏必须形成一个简单多边形。由于这一要求，该问题变得比预期困难得多。测试数据和作者的解法均对应于该问题的以下变体：
- 围栏可以多次经过同一个点，因此不必是简单多边形。
- 仍然禁止多次使用同一条网格线。
- 狼不能被围栏困住。换句话说，矩形外部的网格方格必须在不穿过围栏的情况下对狼是可达的。
作者对这一错误表示歉意，并向所有参加 2016 年 CTU Open Contest 的队伍表示感谢，感谢他们的聪明才智，使得没有队伍尝试提交那个（会被判为正确的）错误解法。这在很大程度上帮助保持了比赛结果的有效性和公平性。