题目描述

考虑一个有 $N$ 个顶点的二叉树，其中顶点编号为 $1, 2, \\ldots, N$。这里，二叉树是一棵根据以下规则构建的树：每个顶点最多有两个孩子。具体而言，二叉树中的每个顶点最多有一个左孩子和一个右孩子。

判断是否存在以顶点 $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$。
否则，按照以下方式将树打印出来。对于每个 $i = 1, 2, \\ldots, N$，第 $i$ 行应该包含 $L_i$ 和 $R_i$，即顶点 $i$ 的左孩子和右孩子的索引。在这里，如果顶点 $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$。