题目背景

在研究某种生物的基因序列时，科学家发现其基因可以表示为一棵二叉树，编号规则如下：

• 根基因编号为 $1$
• 若某个基因编号为 $i$，则它的左子基因编号为 $2i$，右子为 $2i+1$

现在有两份来自不同个体的基因测序数据。科学家想将这两份数据合并：

• 如果某个编号在两份数据中都存在，则合并后的基因值为两值之和
• 如果只在其中一份中存在，则保留该值

为了便于后续分析，需要按前序遍历（根 $\to$ 左子树 $\to$ 右子树）的顺序输出合并后所有非空节点的值。

题目描述

给定两棵二叉树各自的节点信息，输出合并后二叉树的前序遍历结果。

输入格式

第一行一个整数 $n_1$，表示第一棵树的节点个数。

接下来 $n_1$ 行，每行两个整数 $id, val$，表示节点编号和值。

接下来一行一个整数 $n_2$，表示第二棵树的节点个数。

接下来 $n_2$ 行，每行两个整数 $id, val$，表示节点编号和值。

输出格式

输出一行若干整数，表示合并后二叉树的前序遍历结果（每个节点的合并值）。 如果合并后整棵树为空，则输出 -1。

样例输入

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

样例输出

6 7 6 9 2

样例解释

第一棵树：节点 $1(5)$，子节点 $2(3)$、$3(2)$。 第二棵树：节点 $1(1)$，子节点 $2(4)$，节点 $2$ 的子节点 $4(6)$、$5(9)$。

合并后各节点值：

前序遍历顺序：根 $1 \to$ 左子树 $(2 \to 4 \to 5) \to$ 右子树 $(3)$ 输出值依次：$6, 7, 6, 9, 2$

数据范围

$1 \le n_1, n_2 \le 1000$，$1 \le id \le 2000$，$1 \le val \le 10000$。