题目描述

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

输入

1
10

输出

0

---

样例 2

输入

2
3 5
6 8

输出

3
1

---

样例 3

输入

3
1 2 4
7 10
3 5

输出

-1
5
5

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

---

样例 4

输入

4
1 0 3 2
4 6
5 5
7 10

输出

5
5
4
-1

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

---

数据范围与提示

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

子任务编号	分值	$n$	$t_i$	$r_i$
1	20	$1 \leqslant n \leqslant 500$	$0 \leqslant t_i \leqslant 500$	$0 \leqslant r_i \leqslant 500$
2	10	$1 \leqslant n \leqslant 5000$	$t_i = 5000$	$0 \leqslant r_i \leqslant 5000$
3			$0 \leqslant t_i \leqslant 5000$	$r_i = 5000$
4				$0 \leqslant r_i \leqslant 5000$
5	15	$1 \leqslant n \leqslant 2\times 10^5$	$t_i = 10^9$	$0 \leqslant r_i \leqslant 10^9$
6			$0 \leqslant t_i \leqslant 10^9$	$r_i = 10^9$
7	20			$0 \leqslant r_i \leqslant 10^9$