水星上的服务器
题号：NC53306
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
Special Judge, 64bit IO Format: %lld

题目描述

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

输入描述:

第一行有一个整数n。
第二行有n个整数t_1,t_2,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号服务器从不缓存，且2号信道只在第5秒开启，为了让3号服务器拿到补丁，你只能选择在第5秒把补丁发给2号服务器。
若3号服务器首先收到补丁，不妨选择第4秒，3号服务器会将其缓存至第7秒，这样2号和4号服务器都能拿到补丁。

备注:

对于所有数据，。

CC-BY-SA，感谢LOJ分享，译文来自 https://loj.ac/problem/2771