Вы планируете купить квартиру в \(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\) целых чисел \(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
|
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
|
0 2 4 7 8 11 13 14 16 17
|