410791: GYM104114 G Gears

You have an intricate system of $$$n$$$ circular gears connected in a line, with their centers fixed in $$$n$$$ corresponding axles. The $$$i$$$-th axle is fixed on the wall at coordinate $$$x_i$$$ on the (imaginary) number line.

The picture above depicts the example test case.

However, a massive earthquake just hit, and all gears have fallen to the ground, leaving the axles hanging on the wall. Given the radii of the $$$n$$$ gears $$$r_i$$$ and the coordinates of the axles, you are asked to reinstall the system by putting the gears back onto their original places.

The first line of the input contains a single integer $$$n$$$ ($$$1 \leq n \leq 500 \: 000$$$).

The second line of the input contains $$$n$$$ integers $$$x_1, x_2, \ldots, x_n$$$ ($$$1 \leq x_i \leq 10^{16}$$$), the positions of the axles in increasing order.

The third line of the input contains $$$n$$$ integers $$$r_1, r_2, \ldots, r_n$$$ ($$$1 \leq r_i \leq 10^9$$$), the radii of the $$$n$$$ gears.

Output $$$n$$$ numbers $$$s_1, s_2, \ldots, s_n$$$ which indicate the correct placement of the gears on their axle. More specifically, $$$s_i$$$ should be the radius of the gear that will be placed on the $$$i$$$-th axle from the left. For the placement to be valid, every two neighbouring gears must be touching, and $$$s$$$ should be a permutation of $$$r$$$.

It is guaranteed that for all test cases, a solution exists. If multiple solutions exists, you may output any of them.

5
2 8 13 22 30
3 5 5 1 4

5 1 4 5 3