Contest Duration: - (local time) (100 minutes) Back to Home
F - Pre-order and In-order /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

1, 2, \ldots, N と番号づけられた N 個の頂点を持つ二分木を考えます。 ここで、二分木とは各頂点が高々 2 個の子を持つ根付き木です。より具体的には、二分木の各頂点は高々 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


### 出力

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


### 入力例 2

2
2 1
1 2


### 出力例 2

-1


Score : 500 points

### Problem Statement

Consider a binary tree with N vertices numbered 1, 2, \ldots, N. Here, a binary tree is a rooted tree where each vertex has at most two children. Specifically, each vertex in a binary tree has at most one left child and at most one right child.

Determine whether there exists a binary tree rooted at Vertex 1 satisfying the conditions below, and present such a tree if it exists.

• The depth-first traversal of the tree in pre-order is (P_1, P_2, \ldots, P_N).
• The depth-first traversal of the tree in in-order is (I_1, I_2, \ldots, I_N).

### Constraints

• 2 \leq N \leq 2 \times 10^5
• N is an integer.
• (P_1, P_2, \ldots, P_N) is a permutation of (1, 2, \ldots, N).
• (I_1, I_2, \ldots, I_N) is a permutation of (1, 2, \ldots, N).

### Input

Input is given from Standard Input in the following format:

N
P_1 P_2 \ldots P_N
I_1 I_2 \ldots I_N


### Output

If there is no binary tree rooted at Vertex 1 satisfying the conditions in Problem Statement, print -1.
Otherwise, print one such tree in N lines as follows. For each i = 1, 2, \ldots, N, the i-th line should contain L_i and R_i, the indices of the left and right children of Vertex i, respectively. Here, if Vertex i has no left (right) child, L_i (R_i) should be 0.
If there are multiple binary trees rooted at Vertex 1 satisfying the conditions, any of them will be accepted.

L_1 R_1
L_2 R_2
\vdots
L_N R_N


### Sample Input 1

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


### Sample Output 1

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


The binary tree rooted at Vertex 1 shown in the following image satisfies the conditions.

### Sample Input 2

2
2 1
1 2


### Sample Output 2

-1


No binary tree rooted at Vertex 1 satisfies the conditions, so -1 should be printed.