题目描述

给定一棵二叉树的先序遍历和中序遍历，请构造一棵以 $1$ 节点为根的二叉树。这里先序和中序都是一个 $1\sim n$ 的排列。

第 $i$ 行输出节点 $i$ 的左右儿子，儿子为空则输出 $0$。无解输出 -1。

输入格式

第一行输入 $N$

第二行输入 $P_1$ $P_2$ $\ldots$ $P_N$ 代表先序遍历

第三行输入 $I_1$ $I_2$ $\ldots$ $I_N$ 代表中序遍历

输出格式

输出一共输出 $N$ 行，每行两个整数空格隔开分别代表第 $i$ 个点的左右孩子。

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

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

2
2 1
1 2

-1

样例 1 解释

下图中以顶点 $1$ 为根的二叉树满足条件。

提示

• $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)$ 的排列