Problem Description

There are $n$ servers on Mercury and $n-1$ data cables. The $i$-th cable connects server $i$ and server $i+1$ in both directions.

Suppose server $j$ receives a message sent from Earth. You need to transmit the message to all other servers as quickly as possible.

After a server $i$ receives the message from Earth, it can immediately store a copy in its database, and then keep it in its buffer for $t_i$ seconds before deleting it.

Due to some external factors, the $i$-th data cable can transmit information only during the time interval $[l_i,r_i]$. When a cable is active, if at least one of the two servers at its ends still has the message in its buffer, then the other one can obtain the message as well. (After a server receives the message, it will forward the message at the earliest possible time.)

You may choose any time to send the message from Earth to server $j$. In the end, all servers must receive this message. Find the earliest time at which you can send the message. If no feasible solution exists, output $-1$.

Input Format

The first line contains an integer $n$.

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

In the next $n-1$ lines, each line contains two integers $l_i,r_i$.

Output Format

Output $n$ lines, each containing one integer. The number on line $i$ is the answer when $j=i$. If it is impossible, output $-1$.

1
10

0

2
3 5
6 8

3
1

3
1 2 4
7 10
3 5

-1
5
5

4
1 0 3 2
4 6
5 5
7 10

5
5
4
-1

Hint

Sample Explanation

For sample group #3:

If server $1$ receives the patch first, then server $3$ cannot get the patch, because channel $2$ closes before channel $1$ opens. If server $2$ receives the patch at second $5$, then server $3$ can receive the patch immediately. After that, when channel $1$ opens at second $7$, server $1$ will receive the patch. If server $3$ receives the patch at second $5$, then server $2$ can receive the patch immediately. After that, when channel $1$ opens at second $7$, server $1$ will receive the patch.

For sample group #4:

If server $2$ receives the patch first, since server $2$ never caches it and channel $2$ opens only at second $5$, in order for server $3$ to get the patch, you can only choose to send the patch to server $2$ at second $5$. If server $3$ receives the patch first, you may choose second $4$. Server $3$ will cache it until second $7$, so both server $2$ and server $4$ can get the patch.

Constraints

Note: This problem provides only part of the testdata. For the full testdata, please go to LOJ P2771 for judging.

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

Translated by ChatGPT 5