$N$ 個の整数係数一次関数 $f_1(x) = p_1 x + q_1,\ f_2(x) = p_2 x + q_2,...,\ f_N(x) = p_N x + q_N$が与えられます。次の$Q$ 個のクエリに答えてください。
$i$ 番目のクエリでは，整数 $M_i$ が与えられるので、次の条件を満たす長さ $L$ の数列$v_1,\ v_2,\ ...\ v_L$が存在するならば，そのうち$L$ が最小のものを1つ、次の形で出力してください。そのような数列が存在しないとき，:(と出力してください。

$L$
$v_1$ $v_2$ ... $v_L$

• $v_1,\ v_2,\ ...,\ v_L$ はすべて$1$以上 $N$ 以下の自然数
• $k=1,\ 2,\ ...,\ L$に対して、順番に $M_i = f_{v_k}(M_i)$ で置き換えるとき、最終的に $M_i$ が$K$ の倍数となる。

• $1\le N\le 2000$
• $|p_i|,\ |q_i| \le 10^9$
• $1\le Q\le 2000$
• $|M_i|\le 10^{18}$
• $1\le K \le 5000$
• 入力はすべて整数である

小課題

1. (10点) $N\le 5,\ Q = 1$
2. (20点) $N\le 18,\ Q=1$
3. (30点) $N\le 100, Q\le 100$
4. (40点) $Q=1$
5. (400点) 追加の制約はない。

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

$N$
$p_1$ $q_1$
$p_2$ $q_2$
$\vdots$
$p_N$ $q_N$
$Q$ $K$
$M_1$
$M_2$
$\vdots$
$M_Q$

各クエリに対して，問題文の条件を満たす長さ $L$ の数列$v_1,\ v_2,\ ...\ v_L$が存在するならば，そのうち$L$ が最小のものを1つ、次の形で出力して最後に改行してください。そのような数列が存在しないとき，:(と出力してください。

$L$
$v_1$ $v_2$ ... $v_L$