問題文

$1, 2, \\ldots, N$ と番号づけられた $N$ 個の頂点を持つ二分木を考えます。 ここで、二分木とは各頂点が高々 $2$ 個の子を持つ根付き木です。より具体的には、二分木の各頂点は高々 $1$ 個の左の子と高々 $1$ 個の右の子を持ちます。

頂点 $1$ を根とする二分木であって、下記の条件を満たすものが存在するかを判定し、存在する場合はその一例を示してください。

• すべての頂点を深さ優先探索における行きがけ順（pre-order）で並べた列が $(P_1, P_2, \\ldots, P_N)$ である。
• すべての頂点を深さ優先探索における通りがけ順（in-order）で並べた列が $(I_1, I_2, \\ldots, I_N)$ である。

制約

• $2 \\leq N \\leq 2 \\times 10^5$
• $N$ は整数
• $(P_1, P_2, \\ldots, P_N)$ は $(1, 2, \\ldots, N)$ の順列
• $(I_1, I_2, \\ldots, I_N)$ は $(1, 2, \\ldots, N)$ の順列

入力

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

$N$ $P_1$ $P_2$ $\\ldots$ $P_N$ $I_1$ $I_2$ $\\ldots$ $I_N$

出力

問題文中の条件を満たすような頂点 $1$ を根とする二分木が存在しない場合は $\-1$ を出力せよ。
存在する場合は、条件を満たす二分木の一例を下記の形式にしたがって $N$ 行にわたって出力せよ。 すなわち、$i = 1, 2, \\ldots, N$ について、$i$ 行目には頂点 $i$ の左の子の番号 $L_i$ と右の子の番号 $R_i$ を出力せよ。 ただし、左の子（または右の子）を持たない場合は $L_i$（または $R_i$ ）として $0$ を出力せよ。
条件を満たすような頂点 $1$ を根とする二分木が複数存在する場合は、そのうちどれを出力しても正解となる。

$L_1$ $R_1$ $L_2$ $R_2$ $\\vdots$ $L_N$ $R_N$

入力例 1

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

出力例 1

3 6
0 0
0 5
0 0
0 0
4 2

次の画像に示す、頂点 $1$ を根とする二分木が問題文中の条件を満たします。

入力例 2

2
2 1
1 2

出力例 2

-1

問題文中の条件を満たすような頂点 $1$ を根とする二分木は存在しません。よって $\-1$ を出力します。