新生児の世話は簡単な仕事ではありません。常に誰かが赤ちゃんのそばで見守っていなければならず、他にもやるべきことがあり、さらに世話をする人たちも時には眠りたいと考えています。

小さなバイトリンカ（Bajtolinka）の育児には $n$ 人が関わっています。時間区間 $[0, L)$ を $L$ 個の単位区間 $[i, i+1)$ に分割して考えます。各区間について、誰が他の用事で忙しいかを把握しています。他の用事で忙しくない人は、赤ちゃんの世話をするか、眠ることができます。

$n$ 人のそれぞれは、考慮する時間内に最大で1回だけ眠り、目を覚まします。公平を期すため、全員がちょうど同じ時間 $T$ （$T$ は非負の実数）だけ眠るように世話の計画を立てたいと考えています。他の用事は区間 $[i, i+1)$ 全体を占有しますが、睡眠は非負の実数 $a$ （ただし $a+T \le L$）に対して任意の区間 $[a, a+T)$ を占有することができます。

すべての $n$ 人の睡眠を計画し、すべての実数 $x \in [0, L)$ に対して、その瞬間に赤ちゃんの世話ができる人（つまり、眠っておらず、他の用事でも忙しくない人）が少なくとも1人存在するようにできるような、最大の $T$ を求めてください。最適な $T$ （存在する場合）は有理数であることが証明できます。これを既約分数として出力してください。考慮する全期間を通して誰かが赤ちゃんの世話をする計画を立てることができない場合は、$-1$ を出力してください。

入力

入力の1行目には、2つの整数 $n, L$ ($1 \le n \le 18, 1 \le L \le 100\,000$) が与えられます。これらはそれぞれ、バイトリンカの世話をする人数と、考慮する時間区間の長さを表します。 続く $n$ 行には、長さ $L$ の文字列が与えられます。各文字列は文字 X と . （ドット）からなり、各人の他の用事を表します。$i$ 番目の文字は区間 $[i-1, i)$ を表します。

• 文字 X は、その人が他の用事で忙しいことを意味します。
• 文字 . は、その人が空いていることを意味し、眠るか赤ちゃんの世話をすることができます。

出力

計画を立てることができない場合は、出力の1行目に $-1$ を出力してください。そうでない場合は、出力の1行目に既約分数 $x/y$ （$\gcd(x, y) = 1$ かつ $y > 0$）の形式で、最適な世話の計画において各人が眠ることができる最大の睡眠時間を1つ出力してください。

入出力例

入出力例 1

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

4/3

入出力例 2

3 2
..
XX
..

0/1

入出力例 3

1 3
.X.

-1

注記

最初の例では、結果 $4/3$ を得るために、各人はそれぞれ区間 $[0, 4/3), [8/3, 4), [4/3, 8/3)$ で眠る必要があります。

2番目の例では、2人目の人は常に他の用事で忙しいため、眠る時間がありません。

3番目の例では、$x = \pi/2 \approx 1.57$ の時点で、誰も赤ちゃんの世話をすることができません。