You are planning to buy an apartment in a $n$-floor building. The floors are numbered from $1$ to $n$ from the bottom to the top. At first for each floor you want to know the minimum total time to reach it from the first (the bottom) floor.

Let:  $a_i$ for all $i$ from $1$ to $n-1$ be the time required to go from the $i$-th floor to the $(i+1)$-th one (and from the $(i+1)$-th to the $i$-th as well) using the stairs;  $b_i$ for all $i$ from $1$ to $n-1$ be the time required to go from the $i$-th floor to the $(i+1)$-th one (and from the $(i+1)$-th to the $i$-th as well) using the elevator, also there is a value $c$ — time overhead for elevator usage (you need to wait for it, the elevator doors are too slow!). 

In one move, you can go from the floor you are staying at $x$ to any floor $y$ ($x \ne y$) in two different ways:  If you are using the stairs, just sum up the corresponding values of $a_i$. Formally, it will take $\sum\limits_{i=min(x, y)}^{max(x, y) - 1} a_i$ time units.  If you are using the elevator, just sum up $c$ and the corresponding values of $b_i$. Formally, it will take $c + \sum\limits_{i=min(x, y)}^{max(x, y) - 1} b_i$ time units. 

You can perform as many moves as you want (possibly zero).

So your task is for each $i$ to determine the minimum total time it takes to reach the $i$-th floor from the $1$-st (bottom) floor.


-----Input-----

The first line of the input contains two integers $n$ and $c$ ($2 \le n \le 2 \cdot 10^5, 1 \le c \le 1000$) — the number of floors in the building and the time overhead for the elevator rides.

The second line of the input contains $n - 1$ integers $a_1, a_2, \dots, a_{n-1}$ ($1 \le a_i \le 1000$), where $a_i$ is the time required to go from the $i$-th floor to the $(i+1)$-th one (and from the $(i+1)$-th to the $i$-th as well) using the stairs.

The third line of the input contains $n - 1$ integers $b_1, b_2, \dots, b_{n-1}$ ($1 \le b_i \le 1000$), where $b_i$ is the time required to go from the $i$-th floor to the $(i+1)$-th one (and from the $(i+1)$-th to the $i$-th as well) using the elevator.


-----Output-----

Print $n$ integers $t_1, t_2, \dots, t_n$, where $t_i$ is the minimum total time to reach the $i$-th floor from the first floor if you can perform as many moves as you want.


-----Examples-----
Input
10 2
7 6 18 6 16 18 1 17 17
6 9 3 10 9 1 10 1 5

Output
0 7 13 18 24 35 36 37 40 45 

Input
10 1
3 2 3 1 3 3 1 4 1
1 2 3 4 4 1 2 1 3

Output
0 2 4 7 8 11 13 14 16 17

Difficulty: introductory

Starter code:

Solutions:
n, c = list(map(int, input().split()))
a = [int(ai) for ai in input().split()]
b = [int(bi) for bi in input().split()]

dpa, dpb = [0] * n, [0] * n
dpa[1], dpb[1] = a[0], c + b[0]
for i in range(1, n - 1):
    dpa[i + 1], dpb[i + 1] = min(dpa[i], dpb[i]) + a[i], min(dpa[i] + c, dpb[i]) + b[i]

print(*(min(dpa[i], dpb[i]) for i in range(n)))


n, c = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
dp = [[0 for i in range(2)] for i in range(n + 1)]
dp[0][0] = 0
dp[0][1] = c
print(min(dp[0][0], dp[0][1]), end=" ")
for i in range(1, n):
    dp[i][0] = min(dp[i - 1][0] + a[i - 1], dp[i - 1][1] + a[i - 1])
    dp[i][1] = min(dp[i - 1][0] + c + b[i - 1], dp[i - 1][1] + b[i - 1])
    print(min(dp[i][0], dp[i][1]), end=" ")

import sys
def I():
    return sys.stdin.readline().rstrip()

n, c = list(map( int, I().split() ))
a = list( map( int, I().split() ) )
b = list( map( int, I().split() ) )

e = [ 0 ] + [ 1003 * n ] * ( n - 1 )
s = [ 0 ] + [ 1003 * n ] * ( n - 1 )

for i in range( 0, n - 1 ):
    e[ i + 1 ] = min( c + s[ i ] + b[ i ], e[ i ] + b[ i ] )
    s[ i + 1 ] = min( s[ i ], e[ i ] ) + a[ i ]
    if i == 0:
        e[ i + 1 ] += c

ans = [ min( i, j ) for i, j in zip( e, s ) ]
print( *ans )


n, c = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))
sb = [0]
for i in B:
    sb.append(sb[-1] + i)
ans = [0]
hemin = 0
for i in range(1, n):
    tw = min(ans[i - 1] + A[i - 1], hemin + c + sb[i])
    ans.append(tw)
    hemin = min(hemin, ans[i] - sb[i])
print(*ans)


n,c=list(map(int,input().split()))
aa=list(map(int,input().split()))
bb=list(map(int,input().split()))
dp=[[0,c] for i in range(n)]
for i in range(1,n):
    dp[i][0]=min(dp[i-1][0]+aa[i-1],dp[i-1][1]+aa[i-1])
    dp[i][1]=min(dp[i-1][0]+c+bb[i-1],dp[i-1][1]+bb[i-1])
print(*[min(i) for i in dp])


I = lambda: list(map(int, input().split()))

n, c = I()
a = I()
b = I()
dp = [[0, 0] for i in range(300000)]
dp[1][0] = a[0]
dp[1][1] = c + b[0]

for i in range(2, n):
    dp[i][0] = min(dp[i-1][0] + a[i-1], dp[i-1][1] + a[i-1])
    dp[i][1] = min(dp[i-1][0] + c + b[i-1], dp[i-1][1] + b[i-1])
for i in range(n):
    print(min(dp[i][0], dp[i][1]), end = ' ')


n, c = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

dp = [[0]*2 for i in range(n)]
dp[0][1] = c
for i in range(n-1):
    dp[i+1][0] = min(dp[i][0] + a[i], dp[i][1] + a[i])
    dp[i+1][1] = min(dp[i][0] + b[i] + c, dp[i][1] + b[i])
ans = [0]*n
for i in range(n):
    ans[i] = min(dp[i])
print(*ans)

n, c = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
dp = [[0, 0] for i in range(n)]
dp[0] = [0, c]
for i in range(1, n):
    ans1 = dp[i - 1][0] + a[i - 1]
    ans2 = dp[i - 1][1] + b[i - 1]
    dp[i][1] = min(ans2, dp[i - 1][0] + c + b[i - 1])
    dp[i][0] = min(ans1, dp[i][1])
for elem in dp:
    print(min(elem[0], elem[1]), end=" ")

import sys
input = sys.stdin.readline

n,c=list(map(int,input().split()))

A=list(map(int,input().split()))
B=list(map(int,input().split()))

TIME0=[0]*n
TIME1=[0]*n

TIME1[0]=c

for i in range(1,n):
    TIME0[i]=min(TIME0[i-1],TIME1[i-1])+A[i-1]
    TIME1[i]=min(TIME0[i-1]+c+B[i-1],TIME1[i-1]+B[i-1])

ANS=[min(TIME0[i],TIME1[i]) for i in range(n)]
print(*ANS)



n, c = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

T = [[0,0] for i in range(n)]
T[0][1] = c/2
for i in range(1, n):
    T[i][0] = min(T[i-1][0]+A[i-1], T[i-1][1]+B[i-1]+c/2)
    T[i][1] = min(T[i-1][0]+A[i-1]+c/2, T[i-1][1]+B[i-1])

print(" ".join([str(round(i[0])) for i in T]))

n, c=map(int,input().split())
a = [0]+[int(i) for i in input().split()]
b = [0]+[int(i) for i in input().split()]
p = [0] * n
l = [0] * n
t = [0] * n
for i in range(1,n):
    p[i] = a[i] + t[i-1]
    l[i] = b[i] + t[i-1] - (c if t[i-1] == l[i-1] + c else 0)
    l[i] = min(l[i],l[i-1]+b[i])
    t[i] = min(l[i]+c, p[i])
for i in t:
    print(i,end=' ')


n, c = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = 0

w = [[0 for i in range(2)] for i in range(n)]

w[0][1] = c
for i in range(1, n):
    w[i][0] = min(w[i - 1][0] + a[i - 1],
                  w[i - 1][1] + b[i - 1])
    w[i][1] = min(w[i - 1][1] + b[i - 1],
                  w[i][0] + c)

for i in range(n):
    print(min(w[i]), end=' ', flush=False)
print()    

# n: floors
# c: overhead
n, c = map(int, input().split())
a = [0] + list(map(int, input().split())) # stairs time
b = [0] + list(map(int, input().split())) # elevator time

dp = [[0] * 2 for _ in range(n + 1)]
dp[1][0] = 0 # Base case
dp[1][1] = c # Base case
for i in range(2, n + 1):
    dp[i][0] = min(dp[i - 1][0], dp[i - 1][1]) + a[i - 1]
    dp[i][1] = min(dp[i - 1][0] + c, dp[i - 1][1]) + b[i - 1]

print (*[min(u) for u in dp][1:])

"""
NTC here
"""
from sys import stdin, setrecursionlimit
setrecursionlimit(10**7)


def iin(): return int(stdin.readline())
 
 
def lin(): return list(map(int, stdin.readline().split()))


# range = xrange
# input = raw_input


def main():
    n,c=lin()
    s=lin()
    e=lin()
    sol=[[0,0] for i in range(n)]
    sol[0]=[c+e[0],s[0]]
    for i in range(1,n-1):
        sol[i]=[e[i]+min(sol[i-1][0], c+sol[i-1][1]),min(sol[i-1][0],sol[i-1][1])+s[i]]
    ans=[0]+[min(sol[i]) for i in range(n-1)]
    print(*ans)

        







main()
# try:
#     main()
# except Exception as e: print(e)


from math import *

n,k = map(int, input().split())

dp = [[float("inf"),float("inf")] for i in range( 2*10**5 + 5) ]
dp[0] = [0,k]
esc = list(map(int,input().split()))
asc = list(map(int,input().split()))

print(0, end = " ")

for i in range(1, n):
    dp[i][0] = min(dp[i-1]) + esc[i-1]
    dp[i][1] = min(dp[i-1][1], dp[i-1][0] + k) + asc[i-1]

    print(min(dp[i]), end = " ")

import sys
input = sys.stdin.readline
n, c = list(map(int, input().strip().split()))

a = list(map(int, input().strip().split()))
b = list(map(int, input().strip().split()))

stairs = [0 for _ in range(n)]
elevator = [0 for _ in range(n)]
elevator[0] = c

for i in range(1, n):
    stairs[i] = min(elevator[i-1], stairs[i-1])+a[i-1]
    elevator[i] = min(elevator[i-1], stairs[i-1]+c)+b[i-1]
print(' '.join(str(min(elevator[i], stairs[i])) for i in range(n)))



a = input('').split(' ')
n = int(a[0])
c = int(a[1])
t = []
for i in range(n):
    t.append([0,10**5])
a = list(map(int,input('').split(' ')))
b = list(map(int,input('').split(' ')))
print(0,end = ' ')
for i in range(1,n,1):
    t[i][0] = min(t[i-1][1],t[i-1][0]) + a[i-1]
    t[i][1] = min(t[i-1][0]+c,t[i-1][1]) + b[i-1]
    #print(t[i-1],c,b[i-1])
    #print(t[i])
    print(min(t[i][0],t[i][1]), end = ' ')


n,c = list(map(int,input().split()))

lis = []

a = list(map(int,input().split()))
b = list(map(int,input().split()))

asum = 0
bsum = c

for i in range(n):

    lis.append (min(asum,bsum))

    if i == n-1:
        break

    oasum = asum

    asum = min(asum + a[i] , bsum + a[i])

    bsum = min(oasum + b[i] + c , bsum + b[i])

print(" ".join(map(str,lis)))


n, c = map(int, input().split())

S = list(map(int, input().split()))
E = list(map(int, input().split()))

lastS = S[0]
lastE = E[0] + c
print('0 ',end='')
print(min(lastS, lastE), end= ' ')

for i in range(1, n - 1):
    curS = min(lastS + S[i], lastE + S[i])
    curE = min(lastS + c + E[i], lastE + E[i])
    print(min(curS, curE), end=' ')
    lastS = curS
    lastE = curE

#!/usr/bin/env python3
import sys
from math import inf

#lines = stdin.readlines()
def rint():
    return list(map(int, sys.stdin.readline().split()))

def input():
    return sys.stdin.readline().rstrip('\n')

def oint():
    return int(input())


n, c = rint()

a = list(rint())
b = list(rint())

e = 0
ans = [0]
e = [0]*(n+2)
mina = [inf]*(n+2)
mine = [inf]*(n+2)
mina[0] = a[0]
mine[0] = b[0] + c
for i in range(1, n-1):
    mine[i] = b[i] + min(mine[i-1], mina[i-1] + c, mine[i-2]  + mine[i-1])
    mina[i] = a[i] + min(mina[i-1], mine[i-1])

for i in range(n-1):
    ans.append(min(mine[i], mina[i]))

print(*ans)





n, c = list(map(int, input().split()))

a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]

r = [0]
p = [0]
for i in range(n-1):
    x1 = r[-1] + a[i]

    y1 = p[-1] + b[i]
    if i == 0:
        y1 += c
    p.append(y1)

    #print("x1:", x1)
    #print("y1:", y1)

    if r[-1] < p[-1]:
        z1 = r[-1] + b[i] + c
        #print("z1", z1)
        if z1 < y1:
            y1 = z1
            p[-1] = z1
    #print("----")
    if x1 < y1:
        r.append(x1)
    else:
        r.append(y1)

print(*r)
# print(p)



n, c = map(int, input().split())
walk = list(map(int, input().split()))
lift = list(map(int, input().split()))
dpl = [0] * n
dpw = [0] * n
dpl[0] = c
print(0, end=" ")
for i in range(1, n):
    dpl[i] = min(dpw[i - 1] + c, dpl[i - 1]) + lift[i - 1]
    dpw[i] = min(dpw[i - 1], dpl[i - 1]) + walk[i - 1]
    print(min(dpl[i], dpw[i]), end=" ")


# -*- coding: utf-8 -*-

import sys

line_count = 0
for line in sys.stdin.readlines():
    inputs = line.split()
    if line_count == 0:
        n = int(inputs[0])
        c = int(inputs[1])
    elif line_count == 1:
        a = []
        for i in range(n - 1):
            a.append(int(inputs[i]))
    elif line_count == 2:
        b = []
        for i in range(n - 1):
            b.append(int(inputs[i]))
    if line_count == 2:
        break
    line_count += 1

by_stair = [0]
by_elev = [c]
print(0, end = " ")

for i in range(1, n):
    pos_stair = min(by_stair[i - 1] + a[i - 1], by_elev[i - 1] + a[i - 1])
    by_stair.append(pos_stair)
    pos_elev = min(by_stair[i - 1] + c + b[i - 1], by_elev[i - 1] + b[i - 1])
    by_elev.append(pos_elev)
    print(min(pos_stair, pos_elev), end = " ")


n,c=map(int,input().split())
l1=list(map(int,input().split()))
l2=list(map(int,input().split()))
dp=[[0]*2 for _ in range(n+1)]
dp[1][1]=c
for i in range(2,n+1):
    dp[i][0]=min(dp[i-1][0],dp[i-1][1])+l1[i-2]
    dp[i][1]=min(dp[i-1][0]+l2[i-2]+c,dp[i-1][1]+l2[i-2])
for i in range(1,n+1):
    print(min(dp[i]),end=" ")
    

n, c = [int(x) for x in input().split()]
a = list(map(int, input().split()))
b = list(map(int, input().split()))
dpst = [0] * (n + 1)
dplift = [0] * (n + 1)
dpst[2] = a[0]
dplift[2] = c + b[0]
for i in range(3, n + 1):
    dpst[i] = a[i - 2] + min(dpst[i - 1], dplift[i - 1])
    dplift[i] = b[i - 2] + min(c + dpst[i - 1], dplift[i - 1])

for i in range(1, n + 1): print(min(dpst[i], dplift[i]), end = " ")