你正在遊玩熱門電子遊戲《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$ ($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$ 個房間獲得 $2$ 單位經驗值。
2. 用 $6$ 枚遊戲幣購買 $6$ 單位經驗值。
3. 通過第 $2$ 扇門前往第 $2$ 個房間。
4. 在第 $2$ 個房間獲得 $1$ 單位經驗值。
5. 通過第 $2$ 扇門前往第 $1$ 個房間。
6. 通過第 $1$ 扇門逃離。

總共僅需 $6$ 枚遊戲幣。

對於第二個房間：

1. 在第 $2$ 個房間獲得 $1$ 單位經驗值。
2. 用 $4$ 枚遊戲幣購買 $4$ 單位經驗值。
3. 通過第 $3$ 扇門前往第 $3$ 個房間。
4. 在第 $3$ 個房間獲得 $3$ 單位經驗值。
5. 通過第 $4$ 扇門逃離。

僅需 $4$ 枚遊戲幣。

對於第三個房間：

1. 在第 $3$ 個房間獲得 $3$ 單位經驗值。
2. 用 $2$ 枚遊戲幣購買 $2$ 單位經驗值。
3. 通過第 $3$ 扇門前往第 $2$ 個房間。
4. 在第 $2$ 個房間獲得 $1$ 單位經驗值。
5. 通過第 $3$ 扇門前往第 $3$ 個房間。
6. 用 $1$ 枚遊戲幣購買 $1$ 單位經驗值。
7. 通過第 $4$ 扇門逃離。

僅需 $3$ 枚遊戲幣。