Mishka is trying really hard to avoid being kicked out of the university. In particular, he was doing absolutely nothing for the whole semester, miraculously passed some exams so that just one is left.

There were $n$ classes of that subject during the semester and on $i$-th class professor mentioned some non-negative integer $a_i$ to the students. It turned out, the exam was to tell the whole sequence back to the professor. 

Sounds easy enough for those who attended every class, doesn't it?

Obviously Mishka didn't attend any classes. However, professor left some clues on the values of $a$ to help out students like Mishka:   $a$ was sorted in non-decreasing order ($a_1 \le a_2 \le \dots \le a_n$);  $n$ was even;  the following sequence $b$, consisting of $\frac n 2$ elements, was formed and given out to students: $b_i = a_i + a_{n - i + 1}$. 

Professor also mentioned that any sequence $a$, which produces sequence $b$ with the presented technique, will be acceptable.

Help Mishka to pass that last exam. Restore any sorted sequence $a$ of non-negative integers, which produces sequence $b$ with the presented technique. It is guaranteed that there exists at least one correct sequence $a$, which produces the given sequence $b$.


-----Input-----

The first line contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the length of sequence $a$. $n$ is always even.

The second line contains $\frac n 2$ integers $b_1, b_2, \dots, b_{\frac n 2}$ ($0 \le b_i \le 10^{18}$) — sequence $b$, where $b_i = a_i + a_{n - i + 1}$.

It is guaranteed that there exists at least one correct sequence $a$, which produces the given sequence $b$.


-----Output-----

Print $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^{18}$) in a single line.

$a_1 \le a_2 \le \dots \le a_n$ should be satisfied.

$b_i = a_i + a_{n - i + 1}$ should be satisfied for all valid $i$.


-----Examples-----
Input
4
5 6

Output
2 3 3 3

Input
6
2 1 2

Output
0 0 1 1 1 2

Difficulty: interview

Starter code:

Solutions:
#      
import collections, atexit, math, sys, bisect 

sys.setrecursionlimit(1000000)
def getIntList():
    return list(map(int, input().split()))    

try :
    #raise ModuleNotFoundError
    import numpy
    def dprint(*args, **kwargs):
        #print(*args, **kwargs, file=sys.stderr)
        # in python 3.4 **kwargs is invalid???
        print(*args,  file=sys.stderr)
    dprint('debug mode')
except Exception:
    def dprint(*args, **kwargs):
        pass



inId = 0
outId = 0
if inId>0:
    dprint('use input', inId)
    sys.stdin = open('input'+ str(inId) + '.txt', 'r') #标准输出重定向至文件
if outId>0:
    dprint('use output', outId)
    sys.stdout = open('stdout'+ str(outId) + '.txt', 'w') #标准输出重定向至文件
    atexit.register(lambda :sys.stdout.close())     #idle 中不会执行 atexit
    
N, = getIntList()
#print(N)

zb = getIntList()

za1 = [0]
za2 = [zb[0]]

for i in range(1, N//2):
    t1 = zb[i] - za1[-1]
    if t1 <= za2[-1]:
        za1.append(za1[-1])
        za2.append(t1)
        continue
    t2 = zb[i] - za2[-1]
    if t2 >= za1[-1]:
        za1.append(t2)
        za2.append(za2[-1])
        continue
    assert False

zr = za1 + za2[ : :-1]
zs = []
for x in zr:
    zs .append(str(x))
    

r = ' '.join(zs)

print(r)










n = int(input())

b = list(map(int, input().split()))
a1 = [0]
a2 = [b[0]]

for x in b[1:]:
	new_a = a1[-1]
	if x - new_a > a2[-1]:
		new_a = x - a2[-1]
	new_a2 = x - new_a
	a1.append(new_a)
	a2.append(new_a2)
print(*(a1+a2[::-1]))

n=int(input())//2
a=list(map(int,input().split(' ')))
b=[0]*n
a.reverse()
for i in a:
    b.append(i)
mem=b[-1]
c=0
for i in range(n-1):
    if b[-2-i]-c>mem:
        c=b[-2-i]-mem
    b[-2-i]-=c
    b[1+i]+=c
    mem=b[-2-i]
for i in b:
    print(i,end=' ')


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

a = [0] * n

minV = 0
maxV = b[0]

m = n //2

a[n - 1] = b[0]

i = 1
j = n - 2

while(i < m):
  if(b[i] - minV > 0 and b[i] - minV <= maxV):
    a[i] = minV
    a[j] = b[i] - minV
    maxV = min(maxV, b[i] - minV)
  else:
    a[i] = b[i] - maxV
    a[j] = maxV
    minV = max(minV, b[i] - maxV)

  i += 1
  j -= 1

print(' '.join(map(str, a)))


n = int(input())
b = list(map(int, input().split()))
a = [0] * (2 * (len(b)))
a[-1] = b[0]
for i in range(1, len(b)):
    if b[i] - a[i - 1] <= a[-i]:
        a[i] = a[i - 1]
        a[-i - 1] = b[i] - a[i - 1]
    else:
        a[-i - 1] = a[-i]
        a[i] = b[i] - a[-i - 1]
print(*a)


import sys
sys.setrecursionlimit(2000)
from collections import Counter

def __starting_point():

    # single variables
    n = [int(val) for val in input().split()][0]
    b = [int(val) for val in input().split()]

    l = 0
    r = b[0]
    a = [0] * n
    for i in range(n//2):
        a[i] = l
        a[n-1-i] = r
        if(i != n//2-1):
            val = b[i+1]
            summ = l + r
            if(summ == val):
                continue
            elif(summ > val):
                diff = summ - val
                r -= diff
            elif(summ < val):
                diff = val - summ
                l += diff

    for i in a:
        print(i, end=' ')
    print('')
       



__starting_point()

n = int(input())
b = list(map(int, input().split()))
a = [0] * n
c1 = 0; c2 = 10 ** 18
for i in range(n // 2):
    if b[i] - c1 <= c2:
        a[i] = c1
        a[-i - 1] = b[i] - c1
        c2 = b[i] - c1
    else:
        a[-i - 1] = c2
        a[i] = b[i] - c2
        c1 = b[i] - c2
print(' '.join(map(str, a)))


n=int(input())
b=list(map(int,input().split()))
ans=[None]*n
for i in range(n//2):
    if(i==0):
        ans[0]=0
        ans[n-1]=b[0]
    else:
        x=b[i]-ans[i-1]
        if(x>ans[n-i]):
            ans[n-i-1]=ans[n-i]
            ans[i]=b[i]-ans[n-i-1]
        else:
            ans[i]=ans[i-1]
            ans[n-i-1]=b[i]-ans[i]
for i in ans:
    print(i,end=" ")

n = int(input())
s = [int(i) for i in input().split()]
t = [0]*n
t[-1] = s[0]
for i in range(1, n//2):
    if t[n-i] < s[i]-t[i-1]:
        t[i], t[n-1-i] = s[i] - t[n-i], t[n-i]
    else:
        t[i], t[n-1-i] = t[i-1], s[i]-t[i-1]
print(*t)

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

A=[None]*n
A[0]=0
A[n-1]=B[0]

for i in range(1,n//2):
    #A[i-1]<=A[i]
    #B[i-1]-A[i-1]>=B[i]-A[i]
    #A[i]>=B[i]-B[i-1]+A[i-1]

    A[i]=max(A[i-1],B[i]-B[i-1]+A[i-1])
    A[n-1-i]=B[i]-A[i]


for a in A:
    print(a,end=" ")   



#!/usr/bin/env python
# coding: utf-8

# In[14]:


import math
n=int(input())
blist=list(map(int, input().rstrip().split()))


# In[15]:


alist=[0 for i in range(n)]


# In[16]:


alist[0]=0
alist[n-1]=blist[0]

for i in range(1,n//2):
    if blist[i]<=blist[i-1]:
        alist[i]=alist[i-1]
        alist[n-i-1]=blist[i]-alist[i]
    else:
        alist[n-i-1]=alist[n-i]
        alist[i]=blist[i]-alist[n-i-1]
        


# In[17]:


aliststr=[str(i) for i in alist]

print(" ".join(aliststr))


# In[ ]:



from operator import itemgetter
#int(input())
#map(int,input().split())
#[list(map(int,input().split())) for i in range(q)]
#print("YES" * ans + "NO" * (1-ans))
n = int(input())
ai = [0] * n
bi = list(map(int,input().split()))
ai[-1] = bi[0]
for i in range(1,n // 2):
    mina = ai[i-1]
    prev_end = ai[-i]
    num = max(mina,bi[i] - prev_end)
    ai[i] = num
    ai[-i - 1] = bi[i] - num
for i in range(n):
    print(ai[i],end=" ")
    


n = int(input())
b = [int(x) for x in input().split()]
a = [0]
c = [b[0]]
for i in range(1, n // 2):
	if b[i] == b[i - 1]:
		a.append(a[len(a) - 1])
		c.append(c[len(c) - 1])
	elif b[i] > b[i - 1]:
		razn = (b[i] - b[i - 1])
		a.append(a[len(a) - 1] + razn)
		c.append(c[len(c) - 1])
	else:
		razn = (b[i - 1] - b[i])
		c.append(c[len(c) - 1] - razn)
		a.append(a[len(a) - 1])
for x in a:
	print(x, end = ' ')
for j in range(len(c) - 1, -1, -1):
	print(c[j], end = ' ')


import sys
from math import ceil, floor

input = sys.stdin.readline

n = int(input())
ans = [0 for i in range(n)]
a = list(map(int, input().split()))

for i in range(len(a)):
    ans[i] = 0
    ans[n-i-1] = a[i]

for i in range(1, len(a)):
    back = n-i-1
    if ans[i] < ans[i-1]:
        diff = ans[i-1] - ans[i]
        ans[i] += diff
        ans[back] -= diff
    while ans[back] > ans[back+1]:
        diff = ans[back] - ans[back+1]
        ans[i] += diff
        ans[back] -= diff

print(' '.join([str(x) for x in ans]))

n = int(input())
a = list(map(int, input().split()))
s = [0]
for q in range(1, n//2):
    s.append(s[-1]+max(0, a[q]-a[q-1]))
for q in range(n//2, n):
    s.append(a[n-q-1]-s[n-q-1])
print(*s)


n=int(input())
a=list(map(int,input().split()))
b=[-1]*n
b[0]=0;b[n-1]=a[0]
for i in range(1,n//2):
    p,q=0,a[i]
    fl=1
    if p>=b[i-1] and q<=b[n-i] and fl:
        b[i]=p
        b[n-i-1]=q
        fl=0
    p=b[i-1];q=a[i]-b[i-1]
    if p>=b[i-1] and q<=b[n-i] and fl:
        b[i]=p
        b[n-i-1]=q
        fl=0
    q=b[n-i];p=a[i]-b[n-i]
    if p>=b[i-1] and q<=b[n-i] and fl:
        b[i]=p
        b[n-i-1]=q
        fl=0
print(*b)


n = int(input())
b = list(map(int, input().split()))
a = [0]
d = 0
for i in range(n//2-1):
    if b[i+1]>b[i]:
        d+=b[i+1] - b[i]
    a.append(d)
for i in range(n//2-1,-1,-1): a.append(b[i]-a[i])
print(' '.join(list(map(str,a))))

from bisect import bisect_right as br
from bisect import bisect_left as bl
from collections import defaultdict
from itertools import combinations
import sys
import math
MAX = sys.maxsize
MAXN = 10**6+10
MOD = 10**9+7
def isprime(n):
    n = abs(int(n))
    if n < 2:
        return False
    if n == 2: 
        return True    
    if not n & 1: 
        return False
    for x in range(3, int(n**0.5) + 1, 2):
        if n % x == 0:
            return False
    return True

def mhd(a,b,x,y):
    return abs(a-x)+abs(b-y)

def numIN():
    return(list(map(int,sys.stdin.readline().strip().split())))

def charIN():
    return(sys.stdin.readline().strip().split())

t = [(-1,-1)]*1000010

def create(a):
	nonlocal t,n
	for i in range(n,2*n):
		t[i] = (a[i-n],i-n)
	for i in range(n-1,0,-1):
		x = [t[2*i],t[2*i+1]]
		x.sort(key = lambda x:x[0])
		t[i] = x[1]

def update(idx,value):
	nonlocal t,n
	idx = idx+n
	t[idx] = value

	while(idx>1):
		idx = idx//2
		x = [t[2*idx],t[2*idx+1]]
		x.sort(key = lambda x:x[0])
		t[idx] = x[1]


n = int(input())
b = [-1]+list(numIN())
ans = [0]*(n+1)
ans[1] = 0
ans[n] = b[1]
for i in range(2,n//2+1):
	if b[i]<=b[i-1]:
		ans[i] = ans[i-1]
		ans[n-i+1] = b[i]-ans[i]
	else:
		ans[n-i+1] = ans[n-i+2]
		ans[i] = b[i]-ans[n-i+1]
print(' '.join([str(i) for i in ans[1:]]))








n = int(input())
b = list(map(int,input().split()))
a1 = []
a2 = []
cur = 0
last = 10**100
for i in range(len(b)):
    if b[i] - cur > last:
        cur = b[i] - last
    a1 += [cur]
    a2 += [b[i] - cur]
    last = b[i] - cur
print(*(a1 + a2[::-1]))