Hide

Problem N
Leikjahönnun

Languages en is

Gulli is working on a new board game. In the game dice are often rolled to determine what happens next. To have a good idea of how the game plays he needs to know how likely each possible outcome is for a particular set of dice. Can you help him? All dice in the input are unbiased, or in other words, all sides are equally likely to be the outcome.

Input

The first line of the input contains a single integer $n$, the number of dice. Next there are $n$ lines, each describing a single die. The first integer on the $i$-th line, $d_ i$, describes the number of sides on the die. Then there are $d_ i$ integers $x_{i, j}$ separated by spaces describing the number on the $j$-th side of the $i$-th dice.

Output

Print the probabilities of all outcomes when all the dice are rolled and the result is summed up. For each possible outcome $x$ print x p/q where $p/q$ is a reduced fraction giving the probability that the outcome is $x$. You should only print outcomes with a positive probability and the outcomes should be printed in ascending order.

Scoring

Group

Points

Constraints

1

20

$n = 1$, $1 \leq d_ i, x_{i, j} \leq 100$

2

30

$1 \leq n \leq 2$, $1 \leq d_ i, x_{i, j} \leq 100$

3

40

$1 \leq n \leq 7$, $1 \leq d_ i \leq 100$, $1 \leq x_{i,j} \leq 500$

4

10

$1 \leq n \leq 7$, $1 \leq d_ i \leq 100$, $1 \leq x_{i,j} \leq 30\, 000$

Sample Input 1 Sample Output 1
1
8 1 2 3 4 5 6 7 1
1 1/4
2 1/8
3 1/8
4 1/8
5 1/8
6 1/8
7 1/8
Sample Input 2 Sample Output 2
2
6 1 2 3 4 5 6
6 1 2 3 4 5 6
2 1/36
3 1/18
4 1/12
5 1/9
6 5/36
7 1/6
8 5/36
9 1/9
10 1/12
11 1/18
12 1/36
Sample Input 3 Sample Output 3
2
6 1 2 2 3 3 4
6 1 3 4 5 6 8
2 1/36
3 1/18
4 1/12
5 1/9
6 5/36
7 1/6
8 5/36
9 1/9
10 1/12
11 1/18
12 1/36