인기 비디오 게임 Escape the BThouse를 플레이하고 있습니다. 짐작하셨겠지만, 이 게임의 목표는 집에서 탈출하는 것입니다.

이 집은 일렬로 배치되어 $1$부터 $n$까지 번호가 매겨진 $n$개의 방과, 방들 사이에 있는 $n+1$개의 문으로 구성되어 있습니다. $1$번 문은 $1$번 방에 위치한 출구이며, 마찬가지로 $n+1$번 문은 $n$번 방의 출구입니다. 나머지 모든 문 $2 \le i \le n$은 방 $(i-1, i)$를 연결합니다. 당신의 목표는 $1$번 문 또는 $n+1$번 문을 통해 집에서 탈출하는 것입니다.

$i$번째 문을 열려면 최소 $b_i$의 경험치가 필요합니다. 경험치는 방에서 퀘스트를 해결하여 얻을 수 있으며, $i$번 방의 퀘스트를 해결하면 $a_i$의 경험치를 얻습니다. 형식적으로, 퀘스트를 해결하려면 단순히 해당 방에 들어가기만 하면 됩니다. 또한, 게임에는 내장된 현질(monetization) 메커니즘이 있습니다. 언제든지 1 게임 코인으로 1 경험치를 구매할 수 있습니다.

시작할 방을 선택해야 하며, 캐릭터는 해당 방에서 0의 경험치를 가지고 시작합니다. 각 방에 대해, 그 방에서 게임을 시작하여 집을 탈출하는 데 필요한 최소 코인 수를 계산하십시오.

입력

첫 번째 줄에는 정수 $n$ ($1 \le n \le 10^6$)이 주어집니다.

두 번째 줄에는 $n$개의 정수 $a_1, \dots, a_n$ ($0 \le a_i \le 10^9$)이 공백으로 구분되어 주어집니다.

第三 번째 줄에는 $n+1$개의 정수 $b_1, \dots, b_{n+1}$ ($0 \le b_i \le 10^9$)이 공백으로 구분되어 주어집니다.

출력

$n$개의 정수 $ans_1, \dots, ans_n$을 공백으로 구분하여 출력하십시오. 여기서 $ans_i$는 $i$번 방에서 시작하여 게임을 완료하는 데 필요한 최소 코인 수입니다.

서브태스크

이 문제는 다음 요구 사항을 충족하는 8개의 서브태스크로 구성됩니다:

1. $n \le 500$. 12점.
2. $n \le 5000$. 8점.
3. $n \le 2 \cdot 10^5$, $a_i = 0$. 10점.
4. $n \le 2 \cdot 10^5$, $b_1 \le b_2 \le \dots \le b_{n+1}$. 10점.
5. $n \le 2 \cdot 10^5$, $b_i \le 100$. 19점.
6. $n \le 2 \cdot 10^5$. 21점.
7. 원래 문제의 제한 사항. 20점.

예제

입력 1

3
2 1 3
9 8 5 7

출력 1

6 4 3

입력 2

3
1 3 3
10 2 5 6

출력 2

1 1 2

참고

첫 번째 예제를 고려해 봅시다. 1번 방에 대한 최적의 전략은 다음과 같습니다:

1. 1번 방에서 경험치 2를 얻습니다.
2. 6 코인으로 경험치 6을 구매합니다.
3. 2번 문을 통해 2번 방으로 이동합니다.
4. 2번 방에서 경험치 1을 얻습니다.
5. 2번 문을 통해 1번 방으로 이동합니다.
6. 1번 문을 통해 탈출합니다.

총 6 코인만 필요합니다.

2번 방의 경우:

1. 2번 방에서 경험치 1을 얻습니다.
2. 4 코인으로 경험치 4를 구매합니다.
3. 3번 문을 통해 3번 방으로 이동합니다.
4. 3번 방에서 경험치 3을 얻습니다.
5. 4번 문을 통해 탈출합니다.

4 코인만 필요합니다.

3번 방의 경우:

1. 3번 방에서 경험치 3을 얻습니다.
2. 2 코인으로 경험치 2를 구매합니다.
3. 3번 문을 통해 2번 방으로 이동합니다.
4. 2번 방에서 경험치 1을 얻습니다.
5. 3번 문을 통해 3번 방으로 이동합니다.
6. 1 코인으로 경험치 1을 구매합니다.
7. 4번 문을 통해 탈출합니다.

3 코인만 필요합니다.