Balanced Rating Changes
Description
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?
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 $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.
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.
Samples
3
10
-5
-5
5
-2
-3
7
-7
-29
0
3
24
-29
38
-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.