Только что завершился очередной раунд на Codeforces! Раунд собрал \(n\) участников. В соответствии с результатами, ожидаемое изменение рейтинга участника \(i\) равно \(a_i\). Эти изменения рейтинга идеально сбалансированы — их сумма равна \(0\).
К сожалению, из-за небольших технических проблем раунд был объявлен полурейтинговым. Это значит, что все изменения рейтинга должны быть поделены на два.
Однако есть два условия:
- Для каждого участника \(i\) обновлённое изменение рейтинга \(b_i\) должно быть целым числом, максимально близким к \(\frac{a_i}{2}\). Это значит, что либо \(b_i = \lfloor \frac{a_i}{2} \rfloor\), либо \(b_i = \lceil \frac{a_i}{2} \rceil\). В частности, если \(a_i\) чётно, то \(b_i = \frac{a_i}{2}\). Здесь \(\lfloor x \rfloor\) обозначает округление вниз до наибольшего целого числа, не большего \(x\), а \(\lceil x \rceil\) — округление вверх до наименьшего целого числа, не меньшего \(x\).
- Обновлённые изменения рейтинга должны быть идеально сбалансированы — их сумма должна равняться \(0\).
Можете ли вы помочь с этой задачей?
Выходные данные
Выведите \(n\) целых чисел \(b_i\), каждое из которых равно обновлённому изменению рейтинга \(i\)-го участника в порядке ввода.
Для всех \(i\) должно быть верно либо \(b_i = \lfloor \frac{a_i}{2} \rfloor\), либо \(b_i = \lceil \frac{a_i}{2} \rceil\). Сумма всех \(b_i\) должна быть равна \(0\).
Если есть несколько решений, выведите любое. Можно показать, что решение существует для любого корректного ввода.
Примечание
В первом примере, \(b_1 = 5\), \(b_2 = -3\) и \(b_3 = -2\) также является правильным ответом.
Во втором примере есть \(6\) возможных решений, приведено одно из них.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
10
-5
-5
|
5
-2
-3
|
|
2
|
7
-7
-29
0
3
24
-29
38
|
-3
-15
0
2
12
-15
19
|