Another Lottery

Time limit1sMemory limit256 MB

Summary

Each of n players buys tickets across m rounds; round j pays 2^j to one random ticket. For each player, print the reduced fraction for the probability of winning strictly more money than everyone else.

Level: Medium7 of 10
Topics: Probability, Math, Dynamic programming, Combinatorics
Solved: No attempts yet

Problem

Even in times of economic crisis, the people of Byteland still enjoy playing lotteries. With a bit of luck they might shed all their worries and become rich.

The most popular lottery in Byteland consists of $m$ rounds. In each round everyone may buy as many tickets as they wish, and among all tickets sold in that round exactly one is drawn at random, each ticket with equal probability. The owner of that ticket wins the prize money of the round. Because the people of Byteland love powers of two, the prize money for the winner of round $i$ is $2^i$ Bytelandian Dollars.

For each participant, determine the probability that they win more money than anybody else.

Input

The input consists of several test cases. Each test case begins with a line containing two integers $n$ and $m$ : the number of participants and the number of rounds ( $1 \le n \le 10000$ , $1 \le m \le 30$ ).

The next $n$ lines describe the tickets bought by the participants. The $i$ -th of these lines contains $m$ non-negative integers $c_1, \ldots, c_m$ , where $c_j$ ( $1 \le j \le m$ ) is the number of tickets participant $i$ bought in round $j$ . The total number of tickets sold in each round is between $1$ and $10^9$ .

The input ends with a line containing two zeros.

Output

For each test case, print $n$ lines. Line $i$ contains the probability, as a reduced fraction, that participant $i$ wins the most money. Print each fraction in the form numerator / denominator with a single space on each side of the slash (for example 1 / 4; a probability of zero is printed as 0 / 1).

Examples1

Example 1

Input

Expected output