A12893. Balanced Rating Changes

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.

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.