Leikjahönnun

이미지 출처: commons.wikimedia.org

Gulli는 새로운 보드게임을 만들고 있다. 이 게임에서는 다음에 무슨 일이 일어날지 결정하기 위해 주사위를 자주 굴린다. 게임이 어떻게 진행되는지 제대로 파악하려면 특정 주사위 집합에서 가능한 각 결과가 나올 확률을 알아야 한다. Gulli를 도와줄 수 있는가? 입력으로 주어지는 모든 주사위는 공정하다. 다시 말해, 모든 면이 결과로 나올 확률은 같다.

채점

그룹 | 점수 | 제한

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$

입력의 첫째 줄에는 주사위의 개수를 나타내는 하나의 정수 $n$이 주어진다. 다음 $n$개의 줄에는 각각 하나의 주사위에 대한 설명이 주어진다. $i$-번째 줄의 첫 번째 정수 $d_i$은 해당 주사위의 면의 개수를 나타낸다. 이어서 공백으로 구분된 $d_i$개의 정수 $x_{i, j}$이 주어지며, 이는 $i$-번째 주사위의 $j$-번째 면에 적힌 수를 나타낸다.

모든 주사위를 굴린 뒤 그 결과를 합했을 때 나올 수 있는 모든 결과의 확률을 출력한다. 가능한 각 결과 $x$에 대해 x p/q을 출력한다. 여기서 $p/q$은 결과가 $x$일 확률을 나타내는 기약분수이다. 확률이 양수인 결과만 출력해야 하며, 결과는 오름차순으로 출력해야 한다.