问题描述

有 $N$ 个生物站在一个叫做 Snuke 的圆圈中，按逆时针顺序编号为 $1, 2, ..., N$。

当 Snuke $i$ （$1 \leq i \leq N$）在时间 $t$ 收到一个宝石时，$S_i$ 单位时间后，它将在时间 $t+S_i$ 将宝石交给 Snuke $i+1$。这里，Snuke $N+1$ 是 Snuke $1$。

此外，Takahashi 在时间 $T_i$ 将一个宝石交给 Snuke $i$。

对于每个 $i$ （$1 \leq i \leq N$），找到 Snuke $i$ 第一次收到宝石的时间。假设交宝石需要可忽略的时间。

约束条件

• $1 \leq N \leq 200000$
• $1 \leq S_i,T_i \leq 10^9$
• 输入中的所有值均为整数。

---

输入

输入以以下格式从标准输入给出：

$N$ $S_1$ $S_2$ $\ldots$ $S_N$ $T_1$ $T_2$ $\ldots$ $T_N$

输出

打印 $N$ 行。第 $i$ 行（$1 \leq i \leq N$）应该包含 Snuke $i$ 第一次收到宝石的时间。

---

示例输入 1

3
4 1 5
3 10 100

示例输出 1

3
7
8

我们按时间顺序列出三个 Snuke 和 Takahashi 的行动，直到时间 $13$。

时间 $3$：Takahashi 将一个宝石交给 Snuke $1$。

时间 $7$：Snuke $1$ 将一个宝石交给 Snuke $2$。

时间 $8$：Snuke $2$ 将一个宝石交给 Snuke $3$。

时间 $10$：Takahashi 将一个宝石交给 Snuke $2$。

时间 $11$：Snuke $2$ 将一个宝石交给 Snuke $3$。

时间 $13$：Snuke $3$ 将一个宝石交给 Snuke $1$。

之后，它们将继续交宝石，但与答案无关。

---

示例输入 2

4
100 100 100 100
1 1 1 1

示例输出 2

1
1
1
1

注意，$S_i$ 和 $T_i$ 的值可能不是唯一的。

---

示例输入 3

4
1 2 3 4
1 2 4 7

示例输出 3

1
2
4
7

注意，Snuke 可能会同时执行多个交易。特别地，Snuke 可能同时从 Takahashi 和另一个 Snuke 那里收到宝石。

---

示例输入 4

8
84 87 78 16 94 36 87 93
50 22 63 28 91 60 64 27

示例输出 4

50
22
63
28
44
60
64
27