Вы планируете купить квартиру в $$$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$$$-го (нижнего) этажа.