题目描述

题目译自 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
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

数据范围与提示

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