给定一棵二叉搜索树和一个尚未出现在树中的整数 $x$。

请把值为 $x$ 的新节点插入树中，使插入后的树仍满足二叉搜索树的性质，并输出插入后的树。沿着二叉搜索树从根开始比较，就能唯一确定新节点应当接到哪个空孩子位置。输入的树可能为空。

输入格式

第一行一个整数 $n$，表示二叉树的节点数。节点编号为 $1$ 到 $n$，根节点编号为 $1$；当 $n=0$ 时表示空树。

当 $n>0$ 时，第二行包含 $n$ 个整数 $v_1,v_2,\ldots,v_n$，其中 $v_i$ 表示节点 $i$ 保存的值。

接下来 $n$ 行，第 $i$ 行包含两个整数 $l_i,r_i$，分别表示节点 $i$ 的左孩子编号和右孩子编号。编号 $0$ 表示相应孩子不存在。输入保证这些数据构成一棵合法二叉树。

最后一行输入一个整数 $x$，表示需要插入的新值。输入保证 $x$ 尚未出现在树中。

输出格式

输出插入后的二叉搜索树，并按照层序遍历顺序将结果中的节点重新编号为 $1$ 到 $m$。

如果结果为空，只输出一行整数 0。否则第一行输出节点数 $m$，第二行输出重新编号后各节点的值，接下来 $m$ 行分别输出每个节点的左、右孩子编号；编号 0 表示相应孩子不存在。

0
0

1
0
0 0

1
-100000000
0 0
100000000

2
-100000000 100000000
0 2
0 0

5
-60000000 -100000000 60000000 -20000000 20000000
2 3
0 0
4 0
0 5
0 0
100000000

6
-60000000 -100000000 60000000 -20000000 100000000 20000000
2 3
0 0
4 5
0 6
0 0
0 0

数据范围与约定

• 树中的节点数将在 [0, $10^4$ ] 的范围内
• $-10^8$ ≤ v_i ≤ $10^8$
• 所有值 v_i 是 独一无二 的
• $-10^8$ ≤ val ≤ $10^8$
• 保证 val 在原始BST中不存在