Sakurako has found circles arranged on a straight line. The -th circle is positioned at coordinate x_i with a radius r_i. Initially, each circle is divided into two parts: the left half is purple, and the right half is yellow.
Sakurako is allowed to rotate some of the circles, which will swap their colors—so the left half becomes yellow, and the right half becomes purple.
Help Sakurako to determine if it's possible to rotate the circles such that no two circles have overlapping regions of different colors. If it's possible, provide the necessary rotations; otherwise, determine that it is impossible.
The first line contains one integer (1\le n\le 2\cdot 10^5) — the number of circles.
The second line contains integers x_1, x_2, \dots, x_n (1\le x_i\le 10^9) — coordinates of the circles.
The third line contains integers r_1, r_2, \dots, r_n (1\le r_i\le 10^9) — radii of the circles.
Output if it is impossible to rotate the circles as described in the statement. If it is possible, output a string of length where the -th character is "0" if Sakurako does not rotate the -th circle and "1" otherwise.
If there are multiple answers, you are allowed to output any.
Example 1
Example 2
Visualization of the first sample.
In this problem, there are conditional blocks. If your solution works correctly for certain constraints, it will receive a certain number of points. Note that testing is going test by test, but not by blocks.
( points): r_1=r_2=\dots=r_n;
( points): without additional constraints.