메르쿠리의 서버

메르쿠리에 있는 기차역을 제어하는 컴퓨터 시스템은 1번부터 $n$번까지 번호가 매겨진 $n$대의 서버로 이루어져 있다. 서버는 $(n - 1)$개의 양방향 통신 채널로 연결되며, $i$번째 채널은 $i$번 서버와 $(i+1)$번 서버를 잇는다.

지구에서 제어 시스템으로 업데이트 패키지를 보내야 한다. 패키지는 모든 서버에 설치되어야 한다. 지구에서 메르쿠리로 데이터를 보내는 비용이 매우 높으므로, 지구는 패키지를 한 서버에만 보낸다. 그 뒤 패키지는 통신 채널을 통해 다른 모든 서버에 도달해야 하며, 필요하면 다른 서버를 거쳐 갈 수 있다.

메르쿠리에서는 강한 태양 복사 때문에 특정 시간 구간에만 채널로 패키지를 보낼 수 있다. $i$번째 채널은 구간 $[l_i, r_i]$ 동안 패키지를 보낼 수 있다. 패키지는 어떤 채널에서든 즉시 전송된다.

$j$번 서버에 도착한 패키지는 바로 설치되고 메모리 버퍼에 놓인다. 이 버퍼에서 패키지를 다른 서버로 보낼 수 있다. 패키지는 도착한 시점부터 $t_j$초 동안 $j$번 서버의 버퍼에 머문다. 패키지가 버퍼에 있는 동안 아직 패키지가 없는 인접 서버로 가는 채널이 열리면, 패키지는 그 채널로 즉시 전송된다.

패키지에는 중요한 업데이트가 들어 있으므로 배포는 가능한 한 빨리 시작해야 한다.

$1$부터 $n$까지의 각 $i$에 대해, 지구에서 $i$번 서버로 패키지를 보내 모든 서버에 설치할 수 있는지 판단하라. 가능하다면, 모든 서버에 최종적으로 설치되도록 $i$번 서버에 패키지를 보낼 수 있는 가장 이른 음이 아닌 시각을 구하라.

첫 줄에 서버 수 $n$ ($1 \le n \le 200\,000$)이 주어진다.

둘째 줄에는 정수 $t_1, t_2, \ldots, t_n$이 주어진다. $t_j$는 패키지가 $j$번 서버의 버퍼에 머무는 시간이다 ($0 \le t_j \le 10^9$).

이어지는 $(n - 1)$개의 줄마다 두 정수 $l_i$와 $r_i$가 주어진다. 이는 $i$번째 채널로 패키지를 보낼 수 있는 시간 구간의 양 끝이다 ($0 \le l_i \le r_i \le 10^9$).

$n$개의 정수 $a_1, a_2, \ldots, a_n$을 출력하라. $a_i$는 $i$번 서버에 시각 $a_i$에 패키지를 설치하면 최종적으로 모든 서버에 설치되는 가장 작은 음이 아닌 시각이다. 그런 시각이 없으면 $a_i = -1$을 출력하라.

첫 번째 예제에는 서버가 한 대뿐이므로, 업데이트를 설치할 수 있는 가장 이른 시각은 0이다.

두 번째 예제에는 서버가 두 대 있고, 둘 사이에서 패키지를 주고받을 수 있는 구간은 6부터 8까지다. 1번 서버는 패키지를 3초 동안, 2번 서버는 5초 동안 버퍼에 보관한다. 1번 서버에 시각 3에 패키지를 보내면 시각 6에 2번 서버로 전달한다. 마찬가지로 2번 서버에 시각 1에 보내면 시각 6에 1번 서버로 전달한다.

세 번째 예제에서는 1번 서버에 패키지를 보내 3번 서버까지 전달할 수 없다. 2-3 채널이 1-2 채널이 열리기 전에 닫히기 때문이다. 2번 또는 3번 서버에 시각 5에 보낼 수 있다. 이 시각에는 2-3 채널이 열려 있으므로 2번과 3번 서버가 바로 패키지를 받는다. 시각 7에 1-2 채널이 열릴 때 패키지는 아직 2번 서버의 버퍼에 있으므로 1번 서버로 전달된다.

네 번째 예제에서 2번 서버는 패키지를 0초 동안 보관하고, 2-3 채널은 구간 5부터 5까지만 열려 있다. 2번 서버를 거쳐 3번 서버로 전달하려면 시각 5에 2번 서버에 패키지가 도착해 있어야 한다. 3번 서버에 직접 보내려면 시각 4에 보낼 수 있다. 이때 패키지는 시각 7까지 보관되고, 결국 모든 서버에 설치된다.