E. На лифте или по лестнице?
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы планируете купить квартиру в $$$n$$$-этажном здании. Этажи пронумерованы от $$$1$$$ до $$$n$$$ в порядке снизу вверх. Сначала вы хотите узнать для каждого этажа минимально возможное время, необходимое для того, чтобы добраться до него с первого (нижнего) этажа.

Пусть:

  • $$$a_i$$$ для всех $$$i$$$ от $$$1$$$ до $$$n-1$$$ равно времени, необходимому для того, чтобы добраться с $$$i$$$-го этажа на $$$(i+1)$$$-й (а также с $$$(i+1)$$$-го на $$$i$$$-й) по лестнице;
  • $$$b_i$$$ для всех $$$i$$$ от $$$1$$$ до $$$n-1$$$ равно времени, необходимому для того, чтобы добраться с $$$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$$$. Формально, it это займет $$$c + \sum\limits_{i=min(x, y)}^{max(x, y) - 1} b_i$$$ единиц времени.

Вы можете выполнять любое количество ходов (возможно, нулевое).

Таким образом, ваша задача — определить для каждого $$$i$$$ минимально возможное суммарное время, чтобы достичь $$$i$$$-й этаж с $$$1$$$-го (нижнего) этажа.

Входные данные

Первая строка входных данных содержит два целых числа $$$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+1)$$$-й (а также с $$$(i+1)$$$-го на $$$i$$$-й) по лестнице.

Третья строка входных данных содержит $$$n - 1$$$ целое число $$$b_1, b_2, \dots, b_{n-1}$$$ ($$$1 \le b_i \le 1000$$$), где $$$b_i$$$ равно времени, необходимому для того, чтобы добраться с $$$i$$$-го этажа на $$$(i+1)$$$-й (а также с $$$(i+1)$$$-го на $$$i$$$-й) при помощи лифта.

Выходные данные

Выведите $$$n$$$ целых чисел $$$t_1, t_2, \dots, t_n$$$, где $$$t_i$$$ равно минимально возможному суммарному времени, чтобы достичь $$$i$$$-й этаж с первого этажа, если вы можете выполнять любое количество ходов.

Примеры
Входные данные
10 2
7 6 18 6 16 18 1 17 17
6 9 3 10 9 1 10 1 5
Выходные данные
0 7 13 18 24 35 36 37 40 45 
Входные данные
10 1
3 2 3 1 3 3 1 4 1
1 2 3 4 4 1 2 1 3
Выходные данные
0 2 4 7 8 11 13 14 16 17