Problem D. Don't understarve

Author:N. Grebenyuk, A. Usmanov. Translation: A. Logutova.   Time limit:2 sec
Input file:Standard input   Memory limit:256 Mb
Output file:Standard output  


Wilson got lost in a cave N × M cells. However, he has a map with the following notation keys:

'#' — an impassable cell (an abyss, a wall);

'.' — a free cell;

'X' — a wormhole — Wilson can teleport from this cell to any other wormhole with an equal probability;

'S' — a start cell;

'F' — a target cell — Wilson needs to get to this cell (an exit to the surface).

Movement through a wormhole is a risky process, because it takes a lot of Wilson's mind. When the level of his mind become too low, Wilson can be attacked by monsters.

Wilson's mind will be enough exactly for one teleportation. Therefore he wants to know the probability of him getting out of the cave using no more than one wormhole. Naturally, Wilson moves optimally, trying to maximize this probability.

Wilson can move in four directions: up, down, to the right and to the left.

Note that Wilson cannot step into a cell with a wormhole without using it.

Input format

The first line contains two integers N and M — dimensions of the cave.

It follows by N lines, M characters each — map of the cave.

It is guaranteed that there is one 'S' cell, at least one 'F' cell and at least two 'X' cells on the map.

Output format

Print the answer as an irreducible fraction by two integers (for example: if the answer is 50/74, you have to print "25 37").


2 ≤ N, M ≤ 1000

Sample tests

No. Standard input Standard output
2 2
1 1
4 4
2 3
2 5
1 2
3 5
0 1

0.136s 0.019s 15