Lakes

You recently came across an ancient map. Thousands of lakes emerged on the map, both smaller and larger. You couldn't help but think about calculating the probability that, if you swim across an arbitrary lake from west to east starting from any given point, you swim across one of the largest lakes. Write a program to answer your torturous question!

Input Specification

The input contains several test cases. Each test case starts with a line containing three integers: the height of the map (N, 3 ≤ N ≤ 100), the width of the map (M, 3 ≤ M ≤ 100), and the number of crossed distances (D, 1 ≤ D ≤ 500). Each of the next N lines consists of M characters: the “.” (dot) character denotes land, the “O” (capital O) character denotes a piece of a lake. Pieces of the same lake are adjacent only by their four sides. There is no piece of lake at the edges of the map.

Each of the next D lines contains a single integer: the distances you take when crossing a lake.

The end of the input is denoted by a line containing three zeros.

Output Specification

For each distance read from the input, print one line to the standard output, containing a fraction in the form A/B, where A and B are relative primes. The value of the fraction should give the probability for the given distance. If you surely don't swim across one of the largest lakes, then print 0/1 to the output.

The outputs for each distance should be separated by a blank line.

Sample Input

1. 8 10 4
2. ..........
3. .O..OO.OO.
4. ....OO.OO.
5. .OO.......
6. ......OOO.
7. .OOO......
8. .....OOOO.
9. ..........
10. 1
11. 2
12. 3
13. 4
14. 8 10 4
15. ..........
16. .O..OO.OO.
17. ....OO.OO.
18. .OO.......
19. .......OO.
20. .OOO......
21. .O...OOOO.
22. ..........
23. 1
24. 2
25. 3
26. 4
27. 0 0 0

download as text file

Output for Sample Input

1. 0/1
2. 2/3
3. 0/1
4. 1/1
6. 1/2
7. 1/2
8. 1/1
9. 1/1

download as text file

Author

© Dr. Kósa Márk Szabolcs, 2022.