你正在玩一款名为 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$ 枚游戏币。