대홍수

유니산맥에는 $N$개의 지역이 일렬로 늘어서 있고, 각 지역에는 주민이 살고 있다. 유니산맥의 길은 이웃한 지역 사이를 직선으로 잇는 길로만 구성되어 있다. 즉, 이웃하지 않은 지역을 이동하려면 사이에 있는 지역을 모두 거쳐야 한다. 유니산맥의 $i$번째 지역의 높이는 $h\_i$미터이고, $i$번째 지역과 $i+1$번째 지역 사이를 이동하는 데 걸리는 시간은 $t\_i$분이다. 모든 주민은 이웃한 두 지역 사이를 이동할 때 일정한 속도로 이동하며, 이동하는 데 동일한 시간이 걸린다.

어느 날 유니산맥에 큰 홍수가 나기 시작했다. 다행히도 이는 예언된 사실이었고, 유니산맥의 각 지역은 방주를 준비해 두어서 모든 주민들을 살릴 수 있다고 한다. 각 방주는 충분히 커서 탑승 인원에 제한이 없다. 유니산맥 주민들은 정든 유니산맥의 땅을 조금이라도 더 오래 밟고 싶었기 때문에, 이동 중에 물에 잠기지 않고 도달할 수 있는 가장 높은 지역에 있는 방주에 타려고 한다.

수면의 높이는 $0$미터에서 시작해서 $1$분에 $1$미터씩 일정한 속도로 차오른다. 주민이 이동하는 과정에서 수면의 높이보다 낮아지는 경우가 생기면 안 된다. 각 지역의 주민들이 도달할 수 있는 가장 높은 지역의 높이를 구하시오.

첫 번째 줄에 지역의 수 $N$이 주어진다.

두 번째 줄에 각 지역의 높이를 나타내는 $N$개의 정수 $h\_i$가 주어진다.

세 번째 줄에 이웃한 지역 사이를 이동하는 데 걸리는 시간을 나타내는 $N-1$개의 정수 $t\_i$가 주어진다.

한 줄에 $N$개의 정수 $m\_i$를 공백으로 구분하여 출력한다.

$m\_i$는 $i$번째 지역의 주민이 물에 잠기지 않고 도달할 수 있는 가장 높은 지역의 높이이다.

• $2\le N\leq 200,000$
• $0\le h\_i\le 10^9$
• $0< t\_i \le 10^9$