Polycarp invited all his friends to the tea party to celebrate the holiday. He has n cups, one for each of his n friends, with volumes a_1, a_2, ..., a_{n}. His teapot stores w milliliters of tea (w ≤ a_1 + a_2 + ... + a_{n}). Polycarp wants to pour tea in cups in such a way that:  Every cup will contain tea for at least half of its volume  Every cup will contain integer number of milliliters of tea  All the tea from the teapot will be poured into cups  All friends will be satisfied. 

Friend with cup i won't be satisfied, if there exists such cup j that cup i contains less tea than cup j but a_{i} > a_{j}.

For each cup output how many milliliters of tea should be poured in it. If it's impossible to pour all the tea and satisfy all conditions then output -1.


-----Input-----

The first line contains two integer numbers n and w (1 ≤ n ≤ 100, $1 \leq w \leq \sum_{i = 1}^{n} a_{i}$).

The second line contains n numbers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 100).


-----Output-----

Output how many milliliters of tea every cup should contain. If there are multiple answers, print any of them.

If it's impossible to pour all the tea and satisfy all conditions then output -1.


-----Examples-----
Input
2 10
8 7

Output
6 4 

Input
4 4
1 1 1 1

Output
1 1 1 1 

Input
3 10
9 8 10

Output
-1



-----Note-----

In the third example you should pour to the first cup at least 5 milliliters, to the second one at least 4, to the third one at least 5. It sums up to 14, which is greater than 10 milliliters available.

Difficulty: interview

Starter code:

Solutions:
n, w = list(map(int, input().split()))
Cup = list(map(int, input().split()))
Water = []
for a in Cup:
    Water.append((a + 1) // 2)
res = w - sum(Water)
if res < 0:
    print(-1)
else:
    while res > 0:
        i = Cup.index(max(Cup))
        num = min(res, Cup[i] - Water[i])
        Water[i] += num
        res -= num
        Cup[i] = 0
    s = str(Water[0])
    for c in range(1, len(Water)):
        s += " " + str(Water[c])
    print(s)
        


line=input().split()
n=int(line[0])
w=int(line[1])

minsum=0
a=input().split()
for i in range (n):
    a[i]=int(a[i])
    minsum+=(a[i]+1)//2
if (minsum>w):
    print ("-1")
else:
    vols=[str((a[i]+1)//2) for i in range(n)]
    extra=w-minsum
    while (extra>0):
        maxcup=-1
        maxsize=0
        for i in range (n):
            if a[i]>maxsize:
                maxcup=i
                maxsize=a[i]
        if maxcup==-1:
            print(1+" ")
        vols[maxcup]=str(min(maxsize, (maxsize+1)//2 + extra))
        extra -= int(vols[maxcup])-(maxsize+1)//2
        a[maxcup]=-1
    print(" ".join(vols))


n, w = list(map(int, input().split()))
a = list(map(int, input().split()))
arr = []
ans = [0 for _ in range(n)]
for i in range(n):
    ans[i] += (a[i] + 1) // 2
    w -= (a[i] + 1) // 2
    arr.append((a[i], i))
if w < 0:
    print(-1)
else:
    arr = list(reversed(sorted(arr)))
    for a, i in arr:
        d = min(w, a - ans[i])
        ans[i] += d
        w -= d
    print(' '.join(map(str, ans)))


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

n, w = map(int, input().split())
a = list(map(int, input().split()))
s = 0
for i in range(n):
    s += (a[i] + 1) // 2
    a[i] = [a[i], i]
if s > w:
    print(-1)
else:
    res = [[(a[i][0] + 1) // 2, i] for i in range(n)]
    w -= s
    a.sort(reverse=True)
    i = 0
    while w > 0:
        res[a[i][1]][0] = min(a[i][0], res[a[i][1]][0] + w)
        w -= a[i][0] // 2
        i += 1
    for i in range(n):
        print(res[i][0], end=' ')


n, w = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
a_index = [(x, i) for i, x in enumerate(a)]
a_index.sort(reverse=True)
res = [0] * len(a)
for x, i in a_index:
    need = (x+1) // 2
    res[i] = need
    w -= need
    if w < 0:
        print(-1)
        return
if w > 0:
    for x, i in a_index:
        if w == 0:
            break
        need = min(w, x-res[i])
        res[i] += need
        w -= need
print(res[0], end="")
for i in range(1, len(res)):
    print(" " + str(res[i]), end="")
print()

n,w = map(int,input().split())
ai = list(map(int,input().split()))
ai2 = list(range(n))
ai3 = [0] * n
summ = 0
odd_num = 0
for num in ai:
    summ += num - num % 2
    odd_num += num % 2
for i in range(n):
    for j in range(i+1,n):
        if ai[j] > ai[i]:
            temp = ai[i]
            ai[i] = ai[j]
            ai[j] = temp
            temp = ai2[i]
            ai2[i] = ai2[j]
            ai2[j] = temp
w -= summ // 2 + odd_num
if w < 0:
    print(-1)
else:
    for i in range(n):
        temp = min(w,ai[i]//2)
        w -= temp
        ai3[ai2[i]] = ai[i]//2 + ai[i] % 2 + temp
    for num in ai3:
        print(num,end=" ")


def luckyYear():
    n = int(input())
    original = n
    p = -1
    f = 0
    while n > 0:
        f = n % 10
        n //= 10
        p += 1
    f += 1
    f *= 10 ** p
    # print(f)
    print(f - original)


def averageSleepTime():
    n, k = list(map(int, input().split()))
    sleep = list(map(int, input().split()))
    run = 0
    for i in range(k):
        run += sleep[i]
    runavg = [run]
    for i in range(k, n):
        run = run - sleep[i - k] + sleep[i]
        runavg.append(run)
    print('{:.10f}'.format(sum(runavg)/(n-k+1)))

def teaParty():
    n, w = list(map(int, input().split()))
    tea = list(map(int, input().split()))
    fill = []
    [fill.append((t+1)//2) for t in tea]
    if sum(tea) < w or sum(fill) > w:
        print(-1)
        return
    w -= sum(fill)
    sortedPos = [i[0] for i in sorted(enumerate(tea), key = lambda x : x[1])]
    for i in sortedPos[::-1]:
        if w <= 0:
            break
        value = min(tea[i] - fill[i],w)
        fill[i] += value
        w -= value
    print(' '.join(map(str,fill)))



teaParty()


def solve():
    #n = int(input())
    n, w = map(int, input().split())
    a = list(map(int, input().split()))
    #a = [list(map(int, input().split())) for _ in range(n)]
    mp = [[a[i], i] for i in range(n)]
    mp.sort()
    ans = [[mp[i][1], 0] for i in range(n)]
    mi = 0
    for i in range(n):
        t = max(mi, mp[i][0] // 2 + mp[i][0] % 2)
        ans[i][1] = t
        w -= t
        mi = t
    if w < 0:print(-1)
    else:
        for i in range(-1, -n - 1, -1):
            if w > mp[i][0] - ans[i][1]:
                w -= mp[i][0] - ans[i][1]
                ans[i][1] = mp[i][0]
            else:
                ans[i][1] += w
                break
        ans.sort()
        for i in range(n):
            print(ans[i][1], end=' ')

def __starting_point():
    solve()
__starting_point()

def mp():  return list(map(int,input().split()))
def lt():  return list(map(int,input().split()))
def pt(x):  print(x)
def ip():  return input()
def it():  return int(input())
def sl(x):  return [t for t in x]
def spl(x): return x.split()
def aj(liste, item): liste.append(item)
def bin(x):  return "{0:b}".format(x)
def listring(l): return ' '.join([str(x) for x in l])
def ptlist(l): print(' '.join([str(x) for x in l]))

n,w = mp()
a = lt()
b = [int((a[i]+1)/2) for i in range(n)]
if sum(b) <= w:
    d = w - sum(b)
    c = sorted([i for i in range(n)],key=lambda x: a[x],reverse = True)
    while d > 0:
        i = c[0]
        r = min(d,a[i]-b[i])
        d -= r
        b[i] += r 
        c.pop(0)
    ptlist(b)
else:
    pt(-1)


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

import sys
import os
import math

# input_text_path = __file__.replace('.py', '.txt')
# fd = os.open(input_text_path, os.O_RDONLY)
# os.dup2(fd, sys.stdin.fileno())

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

pours = [None] * n

B = []
for i, a in enumerate(A):
    B.append((a, i))
B.sort()

#print(B)
for b in B:
    cup = b[0]
    i = b[1]

    pour_amount = math.ceil(cup / 2)
    pours[i] = pour_amount
    w -= pour_amount

if w < 0:
    print(-1)
else:
    for i in range(n-1, -1, -1):
        cup, idx = B[i]
        if cup > pours[idx]:
            re_pour_amount = min(w, cup - pours[idx])
            pours[idx] += re_pour_amount
            w -= re_pour_amount
    print(*pours)

def main():
    n, w = map(int, input().split())
    a = list(map(int, input().split()))
    res1 = [0 for i in range(n)]
    maxes = a[:]
    maxes.sort()
    for i in range(n):
        res1[i] = (a[i] + 1) // 2
    w -= sum(res1)
    if w < 0:
        print(-1)
        return
    i = -1
    while w > 0:
        maxi = a.index(maxes[i])
        if w > a[maxi] - res1[maxi]:
            w -= (a[maxi] - res1[maxi])
            res1[maxi] = a[maxi]
            a[maxi] = 0
            maxes[i] = 0
        else:
            res1[maxi] += w
            w = 0
        i -= 1
    print(*res1)
main()

import math


n, w = [int(x) for x in input().split()]
l = [int(x) for x in input().split()]
# sorted(l, reverse=False)
qw = l[:]
l.sort(reverse=True)

q = [int(math.ceil(x/2)) for x in l]
sm = sum(q)
if w<sm:
    print(-1)
else:
    rem = w - sm
    er = q[:]
    for x in range(len(q)):
        if rem+q[x]>l[x]:
            rem = rem -(l[x]-q[x])
            q[x] = l[x] 
        else:
            e = []
            q[x] = q[x]+ rem
            #q = zip(l,q)
            for qq in qw:
                inx = l.index(qq)
                e.append(q[inx])
                print(e[-1], end= ' ')
                l[inx] = -111
            


            



# Author: Boonnithi Jiaramaneepinit
# Python Interpreter Version: Python 3.5.2
#
# Note: Educational Codeforces Round 21

import math

def fillTea(water, cups):
    curW = water
    for i in range(len(cups)):
        curW -= math.ceil(cups[i]/2)
        cups[i] = [cups[i], i, math.ceil(cups[i]/2)]
    cups = sorted(cups, key=lambda l:l[0], reverse=True)

    if curW < 0:
        return ['-1']

    # eqLeft = math.floor(curW/len(cups))
    # uneqLeft = curW % len(cups)

    # print(curW, cups)

    # for i in range(len(cups)):
    #     if i < uneqLeft:
    #         cups[i][2] += 1
    #     cups[i][2] = cups[i][2] + eqLeft

    curCup = 0
    while curW > 0:
        curP = min(cups[curCup][0] - cups[curCup][2], curW)
        cups[curCup][2] += curP
        curW -= curP
        curCup += 1

    cups = sorted(cups, key=lambda l:l[1], reverse=False)

    for i in range(len(cups)):
        cups[i] = str(cups[i][2])

    # print(curW, cups)

    if curW < 0:
        return ['-1']

    return cups


'''
3 20
22 2 1
'''
def __starting_point():
    [n, w] = [int(x) for x in input().split()]
    cups = [int(x) for x in input().split()]
    # [n, w] = [3, 20]
    # cups = [22, 2, 1]
    print(' '.join(fillTea(w, cups)))

__starting_point()

n,w = map(int,input().split())
arr = [int(x) for x in input().split()]
arr2 = [(x+1)//2 for x in arr]
s = sum(arr2)
if w<s:
	print(-1)
else:
	w -= s
	while w>0:
		m = max(arr)
		v = arr.index(m)
		while arr2[v]<arr[v] and w>0:
			arr2[v] += 1
			w -= 1
		arr[v] = -1
	for i in range(n):
		print(arr2[i],end=' ')
			



"""import sys
sys.stdin = open("in", "r")"""

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

arr = [[i,int(x)] for i,x in enumerate(input().split())]

arr.sort(reverse=True, key=lambda a: a[1])

res = []
pos = True

for a in arr:
    if(w <= 0):
        pos = False
        break
    res.append([a[0],(a[1]+1)//2])
    w-=(a[1]+1)//2

while(w>0):
    for i in range(n):
        ex = min(w,arr[i][1]-res[i][1])
        w -= ex
        res[i][1]+=ex
        if(w == 0):
            break

res.sort(key=lambda a: a[0])

if(pos):
    print(' '.join(map(lambda a: str(a[1]),res)))
else:
    print(-1)

n, w = map(int, input().split())
Cup = list(map(int, input().split()))
Water = []
for a in Cup:
    Water.append((a + 1) // 2)
res = w - sum(Water)
if res < 0:
    print(-1)
else:
    while res > 0:
        i = Cup.index(max(Cup))
        num = min(res, Cup[i] - Water[i])
        Water[i] += num
        res -= num
        Cup[i] = 0
    s = str(Water[0])
    for c in range(1, len(Water)):
        s += " " + str(Water[c])
    print(s)

import math


class Glass:
    def __init__(self, pos, size, fill=0):
        self.s, self.p, self.f = size, pos, fill


n, w = map(int, input().split())
gls = []
sizes = [int(i) for i in input().split()]
for i in range(n):
    g = Glass(i, sizes[i])
    l = math.ceil(g.s / 2)
    if w >= l:
        g.f, w = l, w - l
        gls.append(g)
    else:
        print(-1)
        return
gls.sort(key=lambda y: y.s)
for i in range(n - 1, -1, -1):
    emp = gls[i].s - gls[i].f
    if w > 0:
        gls[i].f += min(emp, w)
        w -= min(emp, w)
    else:
        break

gls.sort(key=lambda y: y.p)
for i in range(n):
    print(gls[i].f, end=" ")


import sys
from itertools import accumulate

def solve():
    n, w = map(int, input().split())

    a = [int(i) for i in input().split()]
    b = [0] * n

    for i, ai in enumerate(a):
        tmp = (ai + 1) // 2

        w -= tmp
        b[i] += tmp

        if w < 0:
            print(-1)
            return

    ag = [(ai, i) for i, ai in enumerate(a)]
    ag.sort(reverse=True)

    for i in range(n):
        v = ag[i][0]
        k = ag[i][1]
        rem = v - b[k]

        if w > rem:
            w -= rem
            b[k] = v
        else:
            b[k] += w
            break

    print(*b)

def __starting_point():
    solve()
__starting_point()

import math

n,w=input().split(" ")
n=int(n)
w=int(w)

lis=[[int(j),0] for j in input().split(" ")]
for i in range(n):
    lis[i][1]=i

lis=sorted(lis,key= lambda a:a[0],reverse=True)
f=True
ans=[0 for i in range(n)]
#print(ans)
for i in range(n):
    w-=math.ceil(lis[i][0]/2)
    ans[lis[i][1]]=math.ceil(lis[i][0]/2)
    if(w<0):
        f=False
        break

#print(ans)
if(f==True):
    if(w==0):
        for i in range(n):
            print(ans[i],end=" ")
    else:
        for i  in range(n):
            if(w==0):
                break
            if(w>=lis[i][0]-ans[lis[i][1]]):
                w-=lis[i][0]-ans[lis[i][1]]
                ans[lis[i][1]]=lis[i][0]
            else:
                ans[lis[i][1]]+=w
                w=0
        for i in range(n):
            print(ans[i],end=" ")
else:
    print(-1)




n, w = list(map(int, input().split()))
a = list(map(int, input().split()))
b = [(ai + 1) // 2 for ai in a]
r = w - sum(b)
if r < 0:
    print(-1)
else:
    ind = sorted(list(range(n)), key=lambda i: a[i], reverse=True)
    for i in ind:
        c = min(r, a[i] - b[i])
        b[i] += c
        r -= c
        if r == 0:
            break
    print(*b)


n, w = list(map(int,input().split()))
a = list(map(int,input().split()))
b = [(x + 1) // 2 for x in a]
w -= sum(b)
if w > 0:
    a = [(a[i], i) for i in range(n)]
    a.sort(reverse=True)
    for i in range(n):
        x = min(a[i][0] - b[a[i][1]], w)
        w -= x
        b[a[i][1]] += x
        if w == 0:
            break
if w >= 0:
    print(*b)
else:
    print(-1)