Taking care of a newborn is not a simple task. Someone must always be watching over them. There are also other responsibilities, and additionally, the caregivers would like to sleep sometimes.

There are $n$ people involved in raising little Bajtolinka. We consider the time interval $[0, L)$ divided into $L$ unit fragments $[i, i+1)$, and for each of them, we know who is busy with other responsibilities. If a person is not busy with other responsibilities, they can either watch the child or sleep.

Each of the $n$ people will go to sleep and wake up at most once during the considered time. To be fair, we want to plan the care so that everyone sleeps for exactly the same amount of time $T$ (where $T$ is a non-negative real number). Other responsibilities occupy entire fragments $[i, i+1)$, while sleep can occupy any interval $[a, a+T)$ for a non-negative real number $a$ satisfying $a+T \le L$.

Find the largest $T$ for which it is possible to plan the sleep of all $n$ people such that for every real number $x \in [0, L)$, there exists at least one person who can take care of Bajtolinka at time $x$ (i.e., who is not sleeping and not busy with other responsibilities). It can be proven that the optimal $T$ (if it exists) is a rational number. Output it as an irreducible fraction. If it is impossible to arrange a plan such that someone is taking care of the child throughout the entire considered period, output $-1$.

Input

The first line of the input contains two integers $n, L$ ($1 \le n \le 18$, $1 \le L \le 100\,000$), representing the number of people taking care of Bajtolinka and the length of the considered time interval, respectively. The next $n$ lines contain words of length $L$ consisting of the characters X and . (dot), describing the other responsibilities of each person in consecutive time fragments, where the $i$-th character describes the interval $[i-1, i)$. The character X means the person is busy with other responsibilities. The character . means the person is free – they can either sleep or take care of Bajtolinka.

Output

If it is impossible to establish a plan, the single line of output should contain the number $-1$. Otherwise, the single line of output should contain one rational number written in irreducible form $x/y$ ($\gcd(x, y) = 1$ and $y > 0$) – the maximum possible sleep duration for each person that can be achieved with an optimal care plan for Bajtolinka.

Examples

Input 1

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

Output 1

4/3

Input 2

3 2
..
XX
..

Output 2

0/1

Input 3

1 3
.X.

Output 3

-1

Note

In the first example, to obtain the result $4/3$, the people must sleep in the intervals $[0, 4/3)$, $[8/3, 4)$, and $[4/3, 8/3)$, respectively. In the second example, the second person is busy with other responsibilities the entire time, so they have no time to sleep. In the third example, at time $x = \pi/2 \approx 1.57$, no one can take care of Bajtolinka.