You are going on vacation to your local group of exoplanets. In this group, there are $N$ exoplanets lined up in a row. Each exoplanet is an ellipse, consisting of a vertical radius of $h_i$ kilometres and a horizontal radius that is infinitesimal. The $i^{\text{th}}$ exoplanet is $d_i$ kilometres away from the $i+1^{\text{th}}$ exoplanet.

You plan to travel to each exoplanet, starting with exoplanet $1$. On each one, you will stand at the very "top" of the exoplanet, and look to the left (towards exoplanet $i-1$) and to the right (towards exoplanet $i+1$). You are curious about the largest exoplanet that you can see in both directions. Next, you will continue to exoplanet $2$, and so on. The largest exoplanet is defined as the exoplanet with the largest vertical radius.

Note: Exoplanets are solid objects and you will not be able to see some exoplanets afterward if their vertical radius is not large enough. An exoplanet can be seen even if the tip of it can be seen.

Note 2: Your height is $0$ (negligible).

For each exoplanet that you climb up $i$ $(1\le i\le N)$, what is the vertical radius of the largest exoplanet when you look left and when you look right?

Input Specification

The first line will contain the integer $N$ $(1\le N\le 2\times {10}^5)$, the number of exoplanets.

The second line will contain $N$ integers, $h_i$ $(1\le h_i\le {10}^9)$.

The third line will contain $N-1$ integers, $d_i$ $(1\le d_i\le {10}^9,1\le i<N)$, the distance between exoplanet $i$ and $i+1$.

Output Specification

Print $N$ lines. On the $i^{\text{th}}$ line, print two integers, the vertical radius of the largest exoplanet when looking left (towards exoplanet $i-1$) followed by the vertical radius of the largest exoplanet when looking right (towards exoplanet $i+1$). If there is no exoplanet to the left/right, output -1.

Subtasks

Subtask 1 [6%]

$N\le 1000$
$h_i,d_i\le 100$

Subtask 2 [27%]

$h_i,d_i\le 100$

Subtask 3 [67%]

No additional constraints.

Sample Input 1

6
5 2 3 1 4 6
1 1 1 1 1

Sample Output 1

-1 6
5 6
5 6
3 4
5 6
5 -1

Explanation For Sample 1

When you are on exoplanet $2$, the vertical radius of the largest exoplanet you can see to the left is exoplanet $1$, which has a vertical radius of $5$, and to the right is exoplanet $6$, which has a vertical radius of $6$. This is illustrated below with the dashed blue and red lines.

Only the top half of each exoplanet is shown.