あなたは人気ビデオゲーム「Escape the BThouse」をプレイしています。予想通り、目的は家から脱出することです。

この家は $n$ 個の部屋が横一列に並んでおり、部屋番号は $1$ から $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$ の経験値が得られます。形式的には、クエストを解決するにはその部屋に入るだけで十分です。また、このゲームには課金システムが組み込まれており、いつでも好きなだけ経験値を「1経験値につき1ゲーム内コイン」で購入することができます。

あなたは開始する部屋を選択する必要があります。キャラクターはその部屋に $0$ 経験値の状態で出現します。各部屋について、その部屋からゲームを開始して家から脱出するために必要な最小コイン数を計算してください。

入力

入力は以下の形式で与えられます。

$n$ $a_1, \dots, a_n$ $b_1, \dots, b_{n+1}$

最初の行には整数 $n$ ($1 \le n \le 10^6$) が含まれます。 2行目には $n$ 個の整数 $a_1, \dots, a_n$ ($0 \le a_i \le 10^9$) が空白区切りで含まれます。 3行目には $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コインのみ必要です。