您计划购买 $$$n$$$ 层楼的公寓。楼层从下到上编号为 $$$1$$$ 到 $$$n$$$。首先,对于每个楼层,您想知道从第一层(底层)到达该楼层的最短总时间。
让:
- $$$a_i$$$ 对于从 $$$1$$$ 到 $$$n-1$$$ 的所有 $$$i$$$ 是使用楼梯从第 $$$i$$$ 层到第 $$$(i+1)$$$ 层(以及从第 $$$(i+1)$$$ 层到第 $$$i$$$ 层所需的时间;
- $$$b_i$$$ 对于从 $$$1$$$ 到 $$$n-1$$$ 的所有 $$$i$$$ 是使用电梯从第 $$$i$$$ 层到第 $$$(i+1)$$$ 层(以及从第 $$$(i+1)$$$ 层到第 $$$i$$$ 层所需的时间,还有一个值$$$c$$$——电梯使用的时间开销(你需要等待,电梯门太慢了!)。
一次,您可以通过两种不同的方式从您所在的 $$$x$$$ 所在楼层前往任何楼层 $$$y$$$ ($$$x \ne y$$$):
- 如果您使用楼梯,只需将 $$$a_i$$$ 的相应值相加即可。正式来说,需要 $$$\sum\limits_{i=min(x, y)}^{max(x, y) - 1} a_i$$$ 时间单位。
- 如果您使用电梯,只需将 $$$c$$$ 和 $$$b_i$$$ 的相应值相加即可。形式上,需要 $$$c + \sum\limits_{i=min(x, y)}^{max(x, y) - 1} b_i$$$ 时间单位。
您可以执行任意数量的移动(可能为零)。
因此,您的任务是为每个 $$$i$$$ 确定从 $$$1$$$-st(底层)楼层到达 $$$i$$$-th 层所需的最短总时间。
输入
输入的第一行包含两个整数 $$$n$$$ 和 $$$c$$$ ($$$2 \le n \le 2 \cdot 10^5, 1 \le c \le 1000$$$) — 建筑物的楼层数和乘坐电梯的时间开销。
输入的第二行包含 $$$n - 1$$$ 整数 $$$a_1, a_2, \dots, a_{n-1}$$$ ($$$1 \le a_i \le 1000$$$),其中 $$$a_i$$$ 是从 $$$i$$$ 层到第 $$$i$$$ 层所需的时间使用楼梯的第 $$$(i+1)$$$ 个(以及从第 $$$(i+1)$$$ 个到第 $$$i$$$ 个)。
输入的第三行包含 $$$n - 1$$$ 整数 $$$b_1, b_2, \dots, b_{n-1}$$$ ($$$1 \le b_i \le 1000$$$),其中 $$$b_i$$$ 是从 $$$i$$$ 层到第 $$$i$$$ 层所需的时间使用电梯第 $$$(i+1)$$$(以及从第 $$$(i+1)$$$ 到第 $$$i$$$)。
输出
打印 $$$n$$$ 整数 $$$t_1, t_2, \dots, t_n$$$,其中 $$$t_i$$$ 是如果你可以执行任意数量的移动,从第一层到达 $$$i$$$ 层的最短总时间。
示例
输入 #1
10 2 7 6 18 6 16 18 1 17 17 6 9 3 10 9 1 10 1 5
输出 #1
0 7 13 18 24 35 36 37 40 45
输入 #2
10 1 3 2 3 1 3 3 1 4 1 1 2 3 4 4 1 2 1 3
输出 #2
0 2 4 7 8 11 13 14 16 17