Another Codeforces Round has just finished! It has gathered $n$ participants, and according to the results, the expected rating change of participant $i$ is $a_i$. These rating changes are perfectly balanced — their sum is equal to $0$.

Unfortunately, due to minor technical glitches, the round is declared semi-rated. It means that all rating changes must be divided by two.

There are two conditions though:   For each participant $i$, their modified rating change $b_i$ must be integer, and as close to $\frac{a_i}{2}$ as possible. It means that either $b_i = \lfloor \frac{a_i}{2} \rfloor$ or $b_i = \lceil \frac{a_i}{2} \rceil$. In particular, if $a_i$ is even, $b_i = \frac{a_i}{2}$. Here $\lfloor x \rfloor$ denotes rounding down to the largest integer not greater than $x$, and $\lceil x \rceil$ denotes rounding up to the smallest integer not smaller than $x$.  The modified rating changes must be perfectly balanced — their sum must be equal to $0$. 

Can you help with that?


-----Input-----

The first line contains a single integer $n$ ($2 \le n \le 13\,845$), denoting the number of participants.

Each of the next $n$ lines contains a single integer $a_i$ ($-336 \le a_i \le 1164$), denoting the rating change of the $i$-th participant.

The sum of all $a_i$ is equal to $0$.


-----Output-----

Output $n$ integers $b_i$, each denoting the modified rating change of the $i$-th participant in order of input.

For any $i$, it must be true that either $b_i = \lfloor \frac{a_i}{2} \rfloor$ or $b_i = \lceil \frac{a_i}{2} \rceil$. The sum of all $b_i$ must be equal to $0$.

If there are multiple solutions, print any. We can show that a solution exists for any valid input.


-----Examples-----
Input
3
10
-5
-5

Output
5
-2
-3

Input
7
-7
-29
0
3
24
-29
38

Output
-3
-15
0
2
12
-15
19



-----Note-----

In the first example, $b_1 = 5$, $b_2 = -3$ and $b_3 = -2$ is another correct solution.

In the second example there are $6$ possible solutions, one of them is shown in the example output.

Difficulty: interview

Starter code:

Solutions:
n = int(input())
z = 0
for i in range(n):
	x = int(input())
	if x % 2 == 0:
		print(x//2)
	else:
		if z == 1:
			print((x-1)//2)
		else:
			print((x+1)//2)
		z = 1 - z

n=int(input())
d=1
for i in range(n):
    x=int(input())
    if x%2==0:
        print(x//2)
    else:
        if d==1:
            print(int(x/2+0.5))
            d=2
        else:
            print(int(x/2-0.5))
            d=1


n = int(input())
a = [int(input()) for i in range(n)]
b = [0] * n
c = 1
for i in range(n):
    b[i] = a[i] // 2
    if a[i] % 2:
        b[i] += c
        c ^= 1
print('\n'.join(map(str, b)))

n = int(input())
c = 0
while n>0:
    n-=1
    a = int(input())
    if a%2==0:
        print(a//2)
        c-=1
    elif c%2==1:
        print(a//2)
    else:
        print(a//2+1)
    c+=1

N = int(input())

A = []
for _ in range(N):
    A.append(int(input()))
odd_count = 0
for a in A:
    if a % 2 == 0:
        print(a//2)
    else:
        if odd_count % 2 == 0:
            print((a+1)//2)
        else:
            print((a-1)//2)
        odd_count+=1





n = int(input())

foc = 1

for i in range(n):
    a = int(input())
    if (a % 2 == 0):
        print(a // 2)
    else:
        if foc == 1:
            print(a // 2 + 1)
        else:
            print(a // 2)
        foc ^= 1


n = int(input())

cnt = 0

for _ in range(n):
    v = int(input())
    if v % 2 == 0:
        print(v // 2)
    else:
        if cnt % 2 == 0:
            print(v // 2 + 1)
        else:
            print(v // 2)
        cnt += 1

n=int(input())
mod=1
for _ in range(n):
	a=int(input())
	if(a%2)==0:
		print(a//2)
	else:
		print(a//2 + mod)
		mod=1-mod