题目背景

PA 2025 R3A.

题目描述

有一段时间 $[0,l)$ 被等分成 $l$ 份 $[0,1),[1,2),\ldots,[l-1,l)$。

有 $n$ 个人轮流照顾婴儿。$\forall i\in [1,n], j\in [0,l)$，我们知道第 $i$ 个人在时间 $[j,j+1)$ 内是否空闲。如果一个人在一段时间内是空闲的，他可以选择照顾婴儿或睡觉。

在时间段 $[0,l)$ 内，每个人最多可以入睡一次，醒来一次。公平起见，每个人睡眠时长必须相同，设为 $t$（$t\ge 0$）。那么某个人可以在 $[a,a+t)$ 内睡觉，当且仅当他在这段时间内空闲，且 $a+t\le l$。

婴儿在每个时刻都必须有人照顾，换句话说，$\forall x\in [0,l)$，都必须至少有一个人在时刻 $x$ 清醒且空闲。在此前提下，合理安排每个人的睡眠时间，最大化 $t$ 的值。

可以证明，若存在一个合法的 $t$，则 $t$ 的最大值一定是一个有理数。只需要以既约分数的形式输出这个精确值即可。

输入格式

第一行，两个正整数 $n,l$。

接下来 $i$ 行，第 $i$ 行一个长度为 $l$ 的字符串 $s_{i}$。

$\forall 1\le i\le n,\forall 0\le j\lt l$，$s_{i,j}=\texttt{X}$，表示第 $i$ 个人在时段 $[j,j+1)$ 忙碌；否则 $s_{i,j}=\texttt{.}$，表示第 $i$ 个人在时段 $[j,j+1)$ 空闲。

输出格式

如果无法做到「婴儿在每个时刻都必须有人照顾」，输出一行一个 $-1$。

否则，输出一个既约分数 $x/y$（即 $\gcd(x,y)=1,y\gt 0$），表示合法的 $t$ 的最大值。特别地，若 $t$ 的最大值为 $0$，输出 $\texttt{0/1}$。

3 6
..X.XX
.X..X.
X..X..

4/3

3 2
..
XX
..

0/1

1 3
.X.

-1

提示

样例解释

• 样例 $1$ 解释：第 $1,2,3$ 个人分别在 $[0,4/3),[8/3,4),[4/3,8/3)$ 内睡觉。
• 样例 $2$ 解释：第 $2$ 个人没时间睡觉。
• 样例 $3$ 解释：在时刻 $x=\pi/2\approx 1.57$ 时，无人照顾婴儿。

数据范围

• $1\le n\le 18$；
• $1\le l \le 10^5$。