题目描述

题目译自 ROI 2017 Day 2 T2. Серверы на Меркурии

水星上有编号为 $1$ 到 $N$ 的 $N$ 台服务器，这些服务器的通讯呈链式结构。具体来说，我们用 $N-1$ 条信道（视为无向边）连接了这些服务器，第 $i$ 条信道连接 $i$ 号服务器和 $i+1$ 号服务器。
假设 $j$ 号服务器收到了地球发来的补丁。你需要尽快将补丁传输到其他服务器。
一台服务器收到补丁后，会立刻安装这个补丁（安装时间忽略不计），并且将补丁在这台服务器的缓冲区里保留 $t_j$ 秒，之后将其删除。
由于太阳活动的影响，第 $i$ 条通信信道只能在时段 $[l_i, r_i]$（时刻 $l_i$ 到时刻 $r_i$）接通。某条通信信道接通后，如果信道一端的服务器 A 的缓冲区里有补丁，而另一端的服务器 B 没有安装这个补丁，A 就会通过信道向 B 传输这个补丁。请注意，传输补丁的时间忽略不计。注意，你可以任选地球把补丁发给 $j$ 号服务器的时刻。

对于每个 $j$ $(1\le j\le N)$，假设 $j$ 号服务器第一个收到补丁，试求：最早在什么时候把补丁发给 $j$ 号服务器，才能保证所有服务器最后都能装上补丁，如果不可能，请输出 -1。

输入格式

第一行有一个整数 $n$。
第二行有 $n$ 个整数 $t_1,$ $t_2,$ $\ldots,$ $t_n$。
在接下来的 $n-1$ 行中，每行两个整数 $l_i,$ $r_i$。

输出格式

输出 $n$ 行，每行一个整数，表示：最早在什么时候把补丁发给 $j$ 号服务器，才能保证所有服务器最后都能装上补丁。若不可能，请输出 -1。

样例 1

input

1
10

output

0

样例 2

input

2
3 5
6 8

output

3
1

样例 3

input

3
1 2 4
7 10
3 5

output

-1
5
5

如果 $1$ 号服务器首先收到补丁，$3$ 号服务器就无法得到补丁，因为 $2$ 号信道在 $1$ 号信道开启前就关闭了。 如果 $2$ 号服务器在第 $5$ 秒收到补丁，则 $3$ 号服务器可以立即收到补丁，之后，等到第 $7$ 秒时 $1$ 号信道开启时，$1$ 号服务器就会收到补丁。 如果 $3$ 号服务器在第 $5$ 秒收到补丁，则 $2$ 号服务器可以立即收到补丁，之后，等到第 $7$ 秒时 $1$ 号信道开启时，$1$ 号服务器就会收到补丁。

样例 4

input

4
1 0 3 2
4 6
5 5
7 10

output

5
5
4
-1

若 $2$ 号服务器首先收到补丁，由于 $2$ 号服务器从不缓存，且 $2$ 号信道只在第 $5$ 秒开启，为了让 $3$ 号服务器拿到补丁，你只能选择在第 $5$ 秒把补丁发给 $2$ 号服务器。 若 $3$ 号服务器首先收到补丁，不妨选择第 $4$ 秒，$3$ 号服务器会将其缓存至第 $7$ 秒，这样 $2$ 号和 $4$ 号服务器都能拿到补丁。

数据范围与提示

对于所有数据，$0 ⩽ l_i ⩽ r_i ⩽ 10^9$。