Уход за новорожденным — непростая задача. Кто-то всегда должен присматривать за ним. Кроме того, существуют другие обязанности, а опекунам иногда хочется поспать...

В воспитании маленькой Байтолинки участвуют $n$ человек. Мы рассматриваем временной отрезок $[0, L)$, разделенный на $L$ единичных интервалов $[i, i + 1)$, и для каждого из них мы знаем, кто занят другими обязанностями. Если человек не занят другими обязанностями, он может присматривать за ребенком или спать.

Каждый из $n$ человек в рассматриваемый период времени ляжет спать и проснется не более одного раза. Чтобы все было справедливо, мы хотим распределить уход так, чтобы каждый спал ровно $T$ времени (где $T$ — неотрицательное вещественное число). Другие обязанности занимают целые интервалы $[i, i + 1)$, в то время как сон может занимать любой интервал $[a, a + T)$ для неотрицательного вещественного числа $a$, удовлетворяющего условию $a + T \le L$.

Найдите наибольшее $T$, при котором можно спланировать сон всех $n$ человек так, чтобы для каждого вещественного $x \in [0, L)$ существовал хотя бы один человек, который может присматривать за Байтолинкой в момент $x$ (то есть который не спит и не занят другими обязанностями). Можно доказать, что оптимальное $T$ (если оно существует) является рациональным числом. Выведите его в виде несократимой дроби. Если составить план, при котором кто-то присматривает за ребенком в течение всего рассматриваемого периода, невозможно, выведите $-1$.

Входные данные

В первой строке входных данных находятся два целых числа $n, L$ ($1 \le n \le 18$, $1 \le L \le 100\,000$), обозначающие количество людей, присматривающих за Байтолинкой, и длину рассматриваемого временного интервала соответственно.

В следующих $n$ строках находятся слова длины $L$, состоящие из символов X и . (точка), описывающие другие обязанности каждого человека в последовательные моменты времени, где $i$-й символ описывает интервал $[i - 1, i)$.

• Символ X означает, что человек занят другими обязанностями.
• Символ . означает, что человек свободен — он может спать или присматривать за Байтолинкой.

Выходные данные

Если составить план невозможно, в единственной строке вывода должно быть число $-1$. В противном случае в единственной строке вывода должно быть одно рациональное число, записанное в виде несократимой дроби $x/y$ ($\text{НОД}(x, y) = 1$ и $y > 0$) — максимально возможная продолжительность сна каждого человека, которую можно получить при оптимальном планировании ухода за Байтолинкой.

Примеры

Пример 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)$ соответственно.

Во втором примере второй человек все время занят другими обязанностями, поэтому у него нет времени на сон.

В третьем примере в момент $x = \pi/2 \approx 1.57$ никто не может присматривать за Байтолинкой.