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$ 个用空格分隔的整数 $w_1, \ldots, w_N$。第三行包含 $N-1$ 个用空格分隔的整数 $c_1, \ldots, c_{N-1}$。
第三行包含 $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：没有额外限制。