#939. [Lydsy1708月赛]泛化物品

[Lydsy1708月赛]泛化物品

Description

泛化物品是背包问题里的一个概念,泛化物品并没有固定的体积和费用,而是它的费用随着分配给它的体积而变化

。在背包容量为V-1的背包问题中,泛化物品是一个定义域为[0,V)中的整数的函数h,当分配给它的体积为v时,花

费的费用就是h(v)。这个定义有一点点抽象,另一种理解是一个泛化物品就是一个数组h[0..V-1],给它体积v,费

用为h[v]。这就是所谓的泛化物品。定义泛化物品的和:g,h都是泛化物品,若泛化物品f满足f(v)=min{g(k)+h(v-

k)},其中0<=k<=v且0<=k,v-k<n,则称f是g与h的和,即f=g+h。现给定两个定义域均为[0,n)的泛化物品a,b,试求

出c=a+b。

Format

Input

第一行包含一个正整数n(1<=n<=100000),表示定义域中的n。

第二行包含n个整数a_0,a_1,...,a_{n-1}(0<=a_i<n),表示泛化物品a。

第三行包含n个整数b_0,b_1,...,b_{n-1}(0<=b_i<n),表示泛化物品b。

输入数据保证a和b都是0到n-1的随机排列。

Output

对于每组数据输出一行2n-1个整数,依次表示c_0,c_1,...,c_{2n-2}。

Samples

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