とここちゃんは重みつき有向グラフでできた楽器 $G$ と長さ $L$ の数列 $A$ を手に入れました。

楽器 $G$ の頂点には $1$ から $N$ までの番号が順につけられており、$i$ 番目の頂点には音の高さを表す整数 $X_i$ が書かれています。また、$i$ 番目の頂点からは $M_i\ \ (M_i > 0)$ 本の有向辺が張られており、そのうち $j$ 番目の辺は頂点 $V_{i, j}$ に向かい、重み $W_{i, j}$ を持ちます。ここで、$j < k$ ならば $V_{i,j} < V_{i,k}$ です。また、$1 \leq W_{i, j} \leq 100$ かつ $\sum_{j=1}^{M_i} W_{i, j} = 100$ を満たすことが保証されます。

楽器 $G$ に $1$ 以上 $N$ 以下の整数 $a$ を与えると、次の処理手順に従って音が鳴ります。

1. 頂点の番号を表す変数 $v$ を $a$ で初期化する。
2. 音が鳴った回数を表す変数 $c$ を $0$ で初期化する。
3. $X_v$ の音が鳴る。
4. 変数 $c$ を $c + 1$ に更新する。
5. $V_{v, 1}, V_{v, 2}, \dots, V_{v, M_v}$ の中からランダムに $1$ つの頂点を選ぶ。ここで、ある頂点 $V_{v, j}$ が選ばれる確率は $W_{v, j} / 100$ である。
6. 変数 $v$ を 5. で選んだ頂点の番号に更新する。
7. $c = L$ ならば処理を終了する。そうでないなら、3. に戻る。

$k = 1, 2, \dots, N$ について、次の問題に答えてください。

楽器 $G$ に $k$ を与えます。$1$ 番目から $L$ 番目までに鳴った音の高さを表す整数を順に並べた数列を $B$ として、$B$ が $A$ と等しくなる確率を求めてください。答えは必ず有理数になることが証明できます。また、その値を互いに素な整数 $p, q\ \ (p \geq 0, q > 0)$ を用いて $p / q$ として表したとき、そのような $(p, q)$ の組はただ一つしか存在しないことが証明できます。この $p, q$ を求めてください。

• $1 \leq N \leq 10^5$
• $1 \leq L \leq 8$
• $1 \leq A_i \leq N$
• $1 \leq M_i \leq \min(N, 100)$
• $\sum_{i=1}^{N} M_i \leq \min(N^2, 10^5)$
• $1 \leq X_i \leq N$
• $1 \leq V_{i, 1} < V_{i, 2} < \dots < V_{i, M_i} \leq N$
• $1 \leq W_{i,j} \leq 100$
• $\sum_{j=1}^{M_i} W_{i, j} = 100$
• 入力は全て整数

以下の制約を追加したデータセットに正解した場合は $1$ 点が与えられます。

• $M_i \leq 10$
• $L \leq 4$

入力は以下の形式で標準入力から与えられます。

標準出力に $N$ 行出力してください。

$i$ 行目には、$k=i$ のときの答えを互いに素な非負整数 $p, q$ を用いて $p / q$ として表したときの、$p$ と $q$ をこの順に空白区切りで出力してください。