The computer control system for stations on Mercury consists of $n$ servers, numbered from $1$ to $n$. The servers are connected by $(n - 1)$ bidirectional communication channels, where the $i$-th channel connects the $i$-th and $(i + 1)$-th servers.

It is necessary to transmit a software update package from Earth for the control system. The package must be installed on every server. The cost of transmitting the update package from Earth to Mercury is very high, so the package is transmitted from Earth to only one server. Then, the package must be transmitted to all other servers via the communication channels, possibly through other servers.

Due to high solar radiation on Mercury, the update package can only be transmitted through communication channels during certain time intervals. For the $i$-th communication channel, a time interval $[l_i, r_i]$ is known, during which the package can be transmitted through this channel. The package is transmitted through any communication channel instantaneously.

An update package transmitted to the $j$-th server is immediately installed and placed in a special memory buffer, from which it can be transmitted to other servers. The package remains in the memory buffer of the $j$-th server for $t_j$ seconds from the moment it is received. If, while the package is in a server's memory buffer, an opportunity arises to transmit it through a communication channel to an adjacent server where the update package is not yet installed, it is immediately transmitted through that communication channel.

Since the package contains important updates, it is required to start its distribution as early as possible.

You are required to write a program that, for all $i$ from $1$ to $n$, determines whether it is possible to install the update package on all servers by transmitting it from Earth to the $i$-th server. If it is possible, you must determine the minimum non-negative moment in time at which the package can be installed on this server so that, as a result, the update is installed on all servers.

Input

The first line of the input contains $n$ — the number of servers ($1 \le n \le 200\,000$).

The second line contains $n$ integers $t_1, t_2, \dots, t_n$, where $t_j$ is the time the package remains in the memory buffer of the $j$-th server ($0 \le t_j \le 10^9$).

The following $(n-1)$ lines describe the communication channels. To describe the $i$-th channel, two integers $l_i$ and $r_i$ are given — the boundaries of the time interval during which the package can be transmitted through this channel ($0 \le l_i \le r_i \le 10^9$).

Output

The output must contain $n$ integers $a_1, a_2, \dots, a_n$.

The number $a_i$ must be equal to the minimum non-negative moment in time such that, if the update package is installed on the $i$-th server at time $a_i$, the package will eventually be installed on all servers. If no such moment exists for the $i$-th server, you must output $a_i = -1$.

Examples

Input 1

1
10

Output 1

0

Input 2

2
3 5
6 8

Output 2

3
1

Input 3

3
1 2 4
7 10
3 5

Output 3

-1
5
5

Input 4

4
1 0 3 2
4 6
5 5
7 10

Output 4

5
5
4
-1

Note

In the first example, there is only one server, and the minimum suitable time to install the update on it is $0$.

In the second example, there are two servers, and the update can be transmitted between them in the interval from $6$ to $8$. The first server holds the update in its buffer for $3$ units of time, and the second for $5$ units of time. If the update is sent to the first server at time $3$, it will transmit it to the second server at time $6$. Similarly, if the update is sent to the second server at time $1$, it will transmit it to the first server at time $6$.

In the third example, it is impossible to transmit the update to the first server in such a way that it reaches the third server, because channel $2-3$ closes before channel $1-2$ opens. It is possible to send the update to the second or third server at time $5$. At this moment, channel $2-3$ is open, so the second and third servers will receive it immediately. At time $7$, when channel $1-2$ opens, the update will still be in the buffer of the second server and will be transmitted to the first server.

In the fourth example, the second server holds the package for $0$ units of time, and channel $2-3$ is open in the interval $5-5$. To transmit the update through the second server to the third server, it must reach the second server at time $5$. If we want to send the update to the third server, this can be done at time $4$, in which case it will be held until time $7$ and will eventually be installed on all servers.