Gears#12901

Gears

3 seconds
256 megabytes
Hard

You have an intricate system of circular gears connected in a line, with their centers fixed in corresponding axles. The -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 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.

Input

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

The second line of the input contains 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 integers r_1, r_2, \ldots, r_n (1 \leq r_i \leq 10^9), the radii of the gears.

Output

Output 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 -th axle from the left. For the placement to be valid, every two neighbouring gears must be touching, and should be a permutation of .

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

Examples

Example 1

Loading
Loading