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!
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 “
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.
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.
Output for Sample Input
© Dr. Kósa Márk Szabolcs, 2022.
|University of Debrecen; Faculty of Informatics; v. 03/01/2019|