You are going on vacation to your local group of exoplanets. In this group, there are exoplanets lined up in a row. Each exoplanet is an ellipse, consisting of a vertical radius of kilometres and a horizontal radius that is infinitesimal. The exoplanet is kilometres away from the exoplanet.

You plan to travel to each exoplanet, starting with exoplanet . On each one, you will stand at the very "top" of the exoplanet, and look to the left (towards exoplanet ) and to the right (towards exoplanet ). You are curious of the largest exoplanet that you can see in both directions. Next, you will continue to exoplanet , 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 (negligible).

For each exoplanet that you climb up , 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 , the number of exoplanets.

The second line will contain integers, .

The third line will contain integers , , the distance between exoplanet and .

#### Output Specification

Print lines. On the line, print two integers, the vertical radius of the largest exoplanet when looking left (towards exoplanet ) followed by the vertical radius of the largest exoplanet when looking right (towards exoplanet ). If there is no exoplanet to the left/right, output `-1`

.

#### Subtasks

##### Subtask 1 [6%]

##### Subtask 2 [27%]

##### Subtask 3 [67%]

No further 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 , the vertical radius of the largest exoplanet you can see to the left is exoplanet , which has a vertical radius of , and to the right is exoplanet , which has a vertical radius of . This is illustrated below with the dashed blue and red lines.

*Only the top half of each exoplanet is shown.*

## Comments