火星上的计算机控制系统由 $n$ 个服务器组成，编号从 $1$ 到 $n$。服务器通过 $(n-1)$ 条双向通信信道连接，其中第 $i$ 条信道连接第 $i$ 个和第 $(i+1)$ 个服务器。

我们需要从地球向控制系统发送一个软件更新包。该更新包必须安装在每一台服务器上。由于从地球向火星传输更新包的成本非常高，因此更新包只能从地球发送到某一台服务器。随后，必须通过通信信道将更新包传输到所有其他服务器，传输过程中可能需要经过其他服务器。

由于火星上的高太阳辐射，更新包只能在特定的时间段内通过通信信道传输。对于第 $i$ 条通信信道，已知其允许传输更新包的时间段为 $[l_i, r_i]$。更新包通过任何信道传输都是瞬间完成的。

更新包被传输到第 $j$ 个服务器后，会立即安装并存入一个特殊的内存缓冲区，从该缓冲区可以将其传输到其他服务器。更新包在第 $j$ 个服务器的内存缓冲区中停留的时间为 $t_j$ 秒（从接收时刻开始计算）。如果在更新包位于服务器内存缓冲区的期间，出现了通过信道将其传输到尚未安装更新包的相邻服务器的机会，则它会立即通过该信道进行传输。

由于该更新包包含重要的更新，因此要求尽可能早地开始分发。

你需要编写一个程序，对于每个 $i$（从 $1$ 到 $n$），判断是否可以通过将更新包从地球发送到第 $i$ 个服务器来使所有服务器都安装上更新包。如果可以，请确定将更新包安装到该服务器的最小非负时刻，使得最终所有服务器都能安装上更新。

输入格式

第一行包含一个整数 $n$ —— 服务器的数量 ($1 \le n \le 200\,000$)。

第二行包含 $n$ 个整数 $t_1, t_2, \dots, t_n$，其中 $t_j$ 是更新包在第 $j$ 个服务器内存缓冲区中的停留时间 ($0 \le t_j \le 10^9$)。

接下来的 $(n-1)$ 行描述通信信道。描述第 $i$ 条信道时，给出两个整数 $l_i$ 和 $r_i$ —— 允许通过该信道传输更新包的时间段边界 ($0 \le l_i \le r_i \le 10^9$)。

输出格式

输出包含 $n$ 个整数 $a_1, a_2, \dots, a_n$。

数字 $a_i$ 应等于将更新包安装到第 $i$ 个服务器的最小非负时刻，使得最终所有服务器都能安装上更新。如果对于第 $i$ 个服务器不存在这样的时刻，则输出 $a_i = -1$。

样例

样例输入 1

1
10

样例输出 1

0

样例输入 2

2
3 5
6 8

样例输出 2

3
1

样例输入 3

3
1 2 4
7 10
3 5

样例输出 3

-1
5
5

样例输入 4

4
1 0 3 2
4 6
5 5
7 10

样例输出 4

5
5
4
-1

说明

在第一个样例中，只有一个服务器，安装更新的最小合适时间为 $0$。

在第二个样例中，有两个服务器，它们之间可以在 $6$ 到 $8$ 的时间段内传输更新。第一个服务器在缓冲区中保存更新 $3$ 个单位时间，第二个服务器保存 $5$ 个单位时间。如果我们在时刻 $3$ 将更新发送给第一个服务器，它将在时刻 $6$ 将其传给第二个服务器。同样，如果在时刻 $1$ 将更新发送给第二个服务器，它将在时刻 $6$ 将其传给第一个服务器。

在第三个样例中，无法将更新发送给第一个服务器并使其传给第三个服务器，因为信道 $2-3$ 在信道 $1-2$ 开启之前就已经关闭了。可以在时刻 $5$ 将更新发送给第二个或第三个服务器。此时信道 $2-3$ 是开启的，因此第二个和第三个服务器会立即收到更新。在时刻 $7$（信道 $1-2$ 开启时），更新仍保存在第二个服务器的缓冲区中，并会传给第一个服务器。

在第四个样例中，第二个服务器将包保存 $0$ 个单位时间，而信道 $2-3$ 在 $5-5$ 的时间段内开启。为了通过第二个服务器将更新传给第三个服务器，它必须在时刻 $5$ 到达第二个服务器。如果我们想把更新发送给第三个服务器，可以在时刻 $4$ 进行，此时它会一直保存到时刻 $7$，并最终安装在所有服务器上。