宝石接力

题目背景

在一片森林深处，有 $N$ 只小精灵围成一个圆圈，按逆时针方向依次编号为 $1,2,\dots,N$。

乐柠兔会在某些时刻把宝石直接交给指定的小精灵；拿到宝石的小精灵又会按固定的等待时间，把宝石交给下一位。

噜噜想记录：每只小精灵第一次拿到宝石的时间分别是多少。

题目描述

有 $N$ 只小精灵围成一圈，编号为 $1$ 到 $N$（按逆时针方向）。

当小精灵 $i$（$1\le i\le N$）在时刻 $t$ 收到一颗宝石时，它会在 $S_i$ 个时间单位之后，于时刻 $t+S_i$ 把这颗宝石交给小精灵 $i+1$。

这里将小精灵 $N+1$ 视为小精灵 $1$，宝石会沿着圆圈不断传递。交接所需时间忽略不计。

此外，乐柠兔还会在时刻 $T_i$ 直接把一颗宝石交给小精灵 $i$。

对每个 $i$（$1\le i\le N$），请你求出：小精灵 $i$ 第一次收到宝石的最早时刻。

输入格式

第一行输入一个整数 $N$。

第二行输入 $N$ 个整数 $S_1,S_2,\dots,S_N$。

第三行输入 $N$ 个整数 $T_1,T_2,\dots,T_N$。

输出格式

输出 $N$ 行。

第 $i$ 行输出一个整数，表示小精灵 $i$ 第一次收到宝石的时刻。

样例

输入

3
4 1 5
3 10 100

输出

3
7
8

说明

按时间顺序列出关键事件：

• 时刻 $3$：乐柠兔把宝石交给小精灵 $1$，因此 $1$ 第一次收到宝石的时间是 $3$；
• 时刻 $7$：小精灵 $1$ 等待 $S_1=4$ 后把宝石交给 $2$，因此 $2$ 第一次收到宝石的时间是 $7$；
• 时刻 $8$：小精灵 $2$ 等待 $S_2=1$ 后把宝石交给 $3$，因此 $3$ 第一次收到宝石的时间是 $8$；

之后虽然还会继续传递，但不会影响答案。

数据范围与约定

对于 $100$ 的数据，保证：

• $1\le N\le 2\times 10^5$
• $1\le S_i\le 10^9$
• $1\le T_i\le 10^9$
• 输入均为整数