B. Rest Point
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

As is well known, the Earth revolves around the Sun, while the Solar System itself moves through space, and so on.

$$$Andrew-13$$$ became interested in whether the sum of these movements could be exactly zero. Therefore, he asks you to solve the following problem:

It is known that the motion of some object is described by vectors $$$\vec{v_1}, \cdots ,\vec{v_n}$$$. You need to determine whether the sum of these vectors can be equal to the zero vector.

However, instead of the vectors themselves, you are only given their possible lengths (the directions of the vectors may be arbitrary). The lengths are given as segments, that is, vector number $$$i$$$ may have any length belonging to the segment $$$[l_i; r_i]$$$.

For a vector $$$\vec{v} = (x, y, z)$$$, its length is defined as $$$|\vec{v}| = \sqrt{x^2 + y^2 + z^2}$$$.

Input

The first line of the input contains an integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of vectors.

The second line contains $$$n$$$ integers $$$l_1, l_2, \ldots, l_n\, (0\le l_i \le 10^9)$$$.

The next line contains $$$n$$$ integers $$$r_1, r_2, \ldots, r_n\, (l_i \le r_i \le 10^9)$$$.

Output

If it is possible to choose directions for the vectors and choose some lengths from the segments $$$[l_i; r_i]$$$ so that their vector sum is equal to the zero vector, then output in a separate line their lengths $$$a_1, \cdots , a_n$$$ $$$(l_i \le a_i \le r_i)$$$ such that it is possible to choose suitable directions for them so that their sum is the zero vector.

Otherwise, output $$$-1$$$.

Examples
Input
3
2 4 5
10 5 9
Output
3 4 5
Input
2
0 2
1 3
Output
-1