题解

1. 对数组 $b$ 和 $c$ 进行排序,因为前缀和数组是有序的。

2. 通过前缀和的差分,还原出 $b$ 和 $c$ 代表的原始数组,记为 nums1 和 nums2 。

3. 遍历 nums2 ,找到第一个不存在于 nums1 中的数 $x$ ,设其下标为 $i$:

• 如果 $i=n-1$,说明x是原数组的最后一个数,直接将 $x$ 添加到 nums1末尾即可。
• 如果 $i<n-1$,说明x应该插入到 nums1 中,插入位置就是 nums2[i+1] 在 nums1中的位置。

题目描述

小美有一个由$n$个互不相等的正整数构成的数组a，但她一不小心把a弄丢了，他想要重新找到$a$。

好在她并不是一无所有，她还记得以下有关$a$的信息：

1. 他完全记得数组b的样子，并且b是数组 a 删除了某个$a_i$ 后，剩余的部分做前缀和并打乱的结果。

2. 他完全记得数组c的样子，并且c是数组 a 删除了某个 $a_j$ 后，剩余的部分做前缀和并打乱的结果。

（保证两次删除的$a_i$和$a_j$不是同一个a 中的元素）。

请你帮她还原出a数组吧。

补充：前缀和指一个数组的某下标之前的所有数组元素的和（包含其自身）。

输入描述

输入包含三行。

第一行一个正整数$n\ (3\le n \le 10^5)$，表示数组 a 的长度。

第二行$n-1$个正整数 $b_i (1 \le b_i \le 10^{14})$，表示题中所述数组 b。

第二行 $n-1$ 个正整数 $c_i\ (1 \le c_i \le 10^{14})$，表示题中所述数组 c。

（输入保证有唯一解）

输出描述

输出一行$n$个整数，表示你还原出的 a 数组。

样例

输入

4
8 18 14
15 9 1

输出

1 8 6 4