题目名称

最小配对和

题目描述

给定两个长度均为 $n$ 的数列 $a_1,a_2,\cdots,a_n$ 与 $b_1,b_2,\cdots,b_n$ 。从第一个数列中任选一个数，再从第二个数列中任选一个数，将两数相加得到一个和，这样的组合共有 $n \times n$ 种。需要找出其中最小的 $n$ 个组合所形成的和并输出。

输入格式

• 第一行：一个整数 $n$ ，表示数列的长度。
• 第二行：$n$ 个整数，依次表示 $a_1,a_2,\cdots,a_n$ 。
• 第三行：$n$ 个整数，依次表示 $b_1,b_2,\cdots,b_n$ 。

输出格式

输出 $n$ 个整数，为最小的 $n$ 个组合所形成的和，每个数字之间用一个空格隔开。

数据范围

• $1 \leq a_i, b_i \leq 1,000,000,000$ 。
• 对于 30% 的数据，$1 \leq n \leq 100$ 。
• 对于 60% 的数据，$1 \leq n \leq 5,000$ 。
• 对于 100% 的数据，$1 \leq n \leq 100,000$ 。

样例

输入

3
1 2 2
1 1 2

输出

2 2 3