题目描述

Ygod同学运气爆棚中了彩票,他用中彩票的钱买了一栋楼,过上了快乐的收租生活.
但是上门收租实在太麻烦了,有很大一部分时间都用来上楼了.请你帮助他找到从第一层到达每层的最短时间.
这栋大楼共有m层,既有电梯又有步梯,步梯从第i层上到第(i+1)层用时ai秒,电梯第i层上到第(i+1)层用时bi秒.
但是这栋楼有一个奇怪的规定,每乘坐一次电梯必须花费n秒等待电梯,即每次由步梯换乘电梯或首层乘坐电梯需要等待电梯.请你找到从第一层到达每一层的最短时间.

输入描述

输入的第一行包含两个整数m和n（2≤m≤2⋅1e5,1≤n≤1e3）建筑物中的楼层数m和等待电梯的时间n。
输入的第二行包含m-1个整数a1，a2，…，a(m-1)（1≤ai≤1000）其中ai是从第i层到（i + 1）所需的时间。
输入的第三行包含m-1个整数b1，b2，…，b(m-1)（1≤bi≤1000）其中bi是从第i层到（i + 1）所需的时间。

输出描述

打印m个整数t1，t2，…，tm，其中ti是从一楼到达第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 

数据范围

2≤m≤2e5; 1≤n≤1e3;

Stolen by thexx9