Problem Description

On Mercury, there are $n$ servers connected by $n-1$ data lines. The $i$-th data line is bidirectional and connects the $i$-th server with the $(i+1)$-th server.

Suppose server $j$ receives information from Earth. You need to transmit this information to all other servers as quickly as possible.

When a server $i$ receives information from Earth, it can store a copy in its database and then delete it after $t_i$ seconds in the buffer.

Due to external factors, the $i$-th data line can only transmit information during the time interval $[l_i, r_i]$. Once a data line is activated, if one of the servers on either end still has information in its buffer, the other server can also receive this information.

You can choose any moment to send the information to server $j$ from Earth. The goal is to ensure that all servers receive the information. You need to determine the earliest possible time to send the information. If it's not possible to achieve this, output $-1$.

Input Format

The first line contains an integer $n$.

The second line contains $n$ integers $t_1, t_2, \dots, t_n$.

The next $n-1$ lines each contain two integers $l_i$ and $r_i$.

Output Format

Output $n$ lines, each containing an integer. The $i$-th line should represent the answer when $j=i$. If it's not possible, output $-1$.

Sample Input and Output

Input Sample #1

1
10

Output Sample #1

0

Input Sample #2

2
3 5
6 8

Output Sample #2

3
1

Input Sample #3

3
1 2 4
7 10
3 5

Output Sample #3

-1
5
5

Input Sample #4

4
1 0 3 2
4 6
5 5
7 10

Output Sample #4

5
5
4
-1

Notes

Sample Explanation

For Sample Set #3:

If server 1 first receives the patch, server 3 will not be able to get the patch because the 2nd data line closes before the 1st data line opens. If server 2 receives the patch at the 5th second, server 3 can immediately get the patch, and later, when the 1st data line opens at the 7th second, server 1 will receive the patch. If server 3 receives the patch at the 5th second, server 2 can immediately get the patch, and later, when the 1st data line opens at the 7th second, server 1 will receive the patch.

For Sample Set #4:

If server 2 first receives the patch, since server 2 never caches, and the 2nd data line only opens at the 5th second, you can only send the patch to server 2 at the 5th second to ensure server 3 gets the patch. If server 3 first receives the patch, you can choose the 4th second, and server 3 will cache it until the 7th second, allowing both server 2 and server 4 to get the patch.

Data Range

Note: Only partial data is provided; for complete data, please refer to LOJ P2771 for evaluation.

For all data, $0 \le l_i \le r_i \le 10^9$.

见题面 Input 部分

见题面 Output 部分