题目描述

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$ 株植物的最小费用。

3
39 69 33
30 29

2070
2127

3
33 82 36
19 1

1558
676

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

623
4099
4114
6269
6272
6827
8827

提示

样例 1 解释：

使用第一条水渠灌溉前 $2$ 株植物的最小费用是通过使用第一条水渠 $69$ 次，支付 $30 \cdot 69 = 2070$。

灌溉前 $3$ 株植物的最小费用是通过使用第一条水渠 $39$ 次，第二条水渠 $33$ 次，支付 $39 \cdot 30 + 29 \cdot 33 = 2127$。

• 测试点 $4$：$N \leq 200$，并且所有 $w_i \leq 200$。
• 测试点 $5\sim 6$：所有 $w_i \leq 200$。
• 测试点 $7\sim 10$：$N \leq 5000$。
• 测试点 $11\sim 14$：所有 $w_i$ 和 $c_i$ 独立地均匀随机生成。
• 测试点 $15\sim 19$：没有额外限制。