問題文

正整数からなる空でない集合 $S$ に対し $\mathrm{LCM}(S)$ で $S$ が含むすべての要素の最小公倍数を表すものとします。

$N$ 個の互いに相異なる正整数 $A_i\ (1\le i \le N)$ が与えられます。集合 $S$ を $S=\{A_1,\ A_2,\ \dots,\ A_N \}$ と置きます。

以下の条件を満たす $k$ 個の空でない集合の組 $S_1,\ S_2,\ \dots,\ S_k$ が存在するような最小の $k$ を求め、そのような $k$ に対し条件を満たす $S_1,\ S_2,\ \dots,\ S_k$ を構築してください。

そのような $k$ が存在しない場合は $-1$ と出力してください。

• $S_i\ (1\le i \le k)$ の和集合は集合 $S$ に等しい
• $i\neq j$ ならば $S_i,\ S_j$ の積集合（共通部分）は空集合
• $1\le i \le k$ に対し、 $\mathrm{LCM}(S_i) \neq \mathrm{LCM}(S)$ が成り立つ。

この問題では $A_i$ の代わりに $A_i$ の素因数の種類数 $m_i$ と素因数分解 $A_i=p_{i1}^{e_{i1}}p_{i2}^{e_{i2}}\dots p_{im_{i}}^{e_{i{m_i}}}$ が入力で与えられます。

入力

$N$
$m_1$
$p_{11}$ $e_{11}$
$p_{12}$ $e_{12}$
$\vdots$
$p_{1m_1}$ $e_{1m_1}$
$m_2$
$p_{21}$ $e_{21}$
$p_{22}$ $e_{22}$
$\vdots$
$p_{2m_2}$ $e_{2m_2}$
$\vdots$
$m_N$
$p_{N1}$ $e_{N1}$
$p_{N2}$ $e_{N2}$
$\vdots$
$p_{Nm_N}$ $e_{Nm_N}$

• $1\le N \le 10^5$
• $2\le A_i \le 10^{9}$
• $A_i=p_{i1}^{e_{i1}}p_{i2}^{e_{i2}}\dots p_{im_{i}}^{e_{i{m_i}}}$
• $1\le m_i$
• $m_i\ (1\le i \le N)$ の総和は $2\times 10^{5}$ 以下
• $p_{ij}$ は $10^6$ 以下の素数
• $j\neq k$ ならば $p_{ij}\neq p_{ik}$
• $1\le e_{ij}$
• $i\neq j$ ならば $A_i \neq A_j$
• 与えられる入力はすべて整数

出力

条件を満たす $S_i\ (1\le i \le k)$ の組が存在するような $k$ が存在しない場合は $-1$ とだけ出力してください。

存在する場合は $1$ 行目に最小の $k$ を出力し、 $n_i=|S_i|$ として、 $2$ 行目以降に以下の形式で $S_i\ (1\le i \le k)$ について出力してください。

条件を満たす $S_i\ (1\le i \le k)$ の組が複数存在する場合はいずれを出力してもかまいません。

また、 $S_i$ の要素 $S_{i1},\ S_{i2},\ \dots,\ S_{in_i}$ についてはどのような順序で出力してもかまいません。

$k$
$n_1$ $S_{11}$ $S_{12}$ $\dots$ $S_{1n_1}$
$n_2$ $S_{21}$ $S_{22}$ $\dots$ $S_{2n_2}$
$\vdots$
$n_k$ $S_{k1}$ $S_{k2}$ $\dots$ $S_{kn_k}$

最後に改行してください。

サンプル

3
1
3 1
1
2 2
1
7 1

2
2 3 4
1 7

4
2
2 1
3 2
3
2 1
3 2
5 1
2
2 2
3 2
2
2 2
5 1

3
2 18 90
1 20
1 36

3
1
2 1
1
3 1
2
2 1
3 1

-1