Bessie 的花园里有 $N$ 株植物，从左到右编号为 $1$ 到 $N$ ($2\leq N\leq 5\cdot 10^5$)。Bessie 知道第 $i$ 株植物至少需要 $w_i$ ($0\leq w_i \leq 10^6$) 单位的水。Bessie 有一套非常奇特的灌溉系统，包含 $N-1$ 条运河，编号为 $1$ 到 $N-1$。每条运河 $i$ 都有一个单位成本 $c_i$ ($1\le c_i\le 10^6$)，Bessie 可以支付 $c_i k$ 的费用，为植物 $i$ 和 $i+1$ 各提供 $k$ 单位的水，其中 $k$ 是非负整数。Bessie 很忙，可能没有时间使用所有的运河。对于每个 $2\leq i \leq N$，请计算仅使用前 $i-1$ 条运河为植物 $1$ 到 $i$ 供水所需的最小成本。

输入格式

第一行包含一个整数 $N$。 第二行包含 $N$ 个空格分隔的整数 $w_1, \ldots, w_N$。 第三行包含 $N-1$ 个空格分隔的整数 $c_1, \ldots, c_{N-1}$。

输出格式

输出 $N-1$ 行，每行一个整数。第 $i-1$ 个整数表示使用前 $i-1$ 条运河为前 $i$ 株植物供水所需的最小成本。

样例

样例输入 1

3
39 69 33
30 29

样例输出 1

2070
2127

样例输入 2

3
33 82 36
19 1

样例输出 2

1558
676

样例输入 3

8
35 89 44 1 35 3 62 50
7 86 94 62 63 9 49

样例输出 3

623
4099
4114
6269
6272
6827
8827

数据范围

• 测试点 4：$N \leq 200$，且所有 $w_i \leq 200$。
• 测试点 5-6：所有 $w_i \leq 200$。
• 测试点 7-10：$N \leq 5000$。
• 测试点 11-14：所有 $w_i$ 和 $c_i$ 均独立且均匀随机生成。
• 测试点 15-19：无附加限制。