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.
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 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.
Example 1