C. Тренировка перед олимпиадой
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Маши и Оли скоро важная командная олимпиада. В честь этого Маша, для разминки, предложила сыграть Оле в следующую игру:

Есть массив $$$a$$$ размера $$$n$$$. Первой ходит Маша, игроки ходят по-очереди. Каждый ход описывается следующей последовательностью действий:

$$$\bullet$$$ Если размер массива равен $$$1$$$ — игра завершается.

$$$\bullet$$$ Игрок, который сейчас ходит, выбирает два различных индекса $$$i$$$, $$$j$$$ ($$$1 \le i, j \le |a|$$$), и проделывает следующую операцию — удаляет $$$a_i$$$ и $$$a_j$$$ из массива и добавляет в массив число равное $$$\lfloor \frac{a_i + a_j}{2} \rfloor \cdot 2$$$. Иными словами, сначала делит сумму чисел $$$a_i$$$, $$$a_j$$$ на $$$2$$$ с округлением вниз, после чего результат умножает на $$$2$$$.

Маша стремится максимизировать итоговое число, Оля же — минимизировать.

Маша и Оля решили сыграть на каждом непустом префиксе первоначального массива $$$a$$$, и попросили вас об одной помощи.

Для каждого $$$k = 1, 2, \ldots, n$$$ ответьте на следующий вопрос. Пусть в игре присутствуют только первые $$$k$$$ элементов массива $$$a$$$, соответственно с индексами $$$1, 2, \ldots, k$$$. Какое число тогда останется при оптимальной игре обоих игроков?

Входные данные

Первая строка содержит целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит единственное целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — размер массива.

Во второй строке содержится $$$n$$$ целых чисел $$$a_1,a_2, \ldots,a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — массив, на котором играют Маша и Оля.

Гарантируется, что сумма $$$n$$$ по всем входным данным не превосходит $$$10^5$$$.

Выходные данные

Для каждого набора входных данных выведите $$$n$$$ целых чисел. $$$k$$$-е из этих чисел должно быть равно числу, которое останется в конце при оптимальной игре обоих, на массиве, состоящем из первых $$$k$$$ элементов массива $$$a$$$.

Пример
Входные данные
4
1
31
6
6 3 7 2 5 4
3
3 10 11
5
7 13 11 19 1
Выходные данные
31 
6 8 16 18 22 26 
3 12 24 
7 20 30 48 50
Примечание

В третьем наборе входных данных для префикса длины $$$1$$$ ответ $$$3$$$. Для префикса длины $$$2$$$ у Маши есть один вариант для хода, поэтому ответ $$$12$$$. Для префикса длины $$$3$$$ у Маши есть три возможных хода: она выбирает $$$3$$$ и $$$10$$$, тогда число в конце $$$22$$$, $$$3$$$ и $$$11$$$, тогда число в конце $$$24$$$, $$$10$$$ и $$$11$$$, тогда число в конце $$$22$$$, значит Маша выберет $$$3$$$ и $$$11$$$ и получит $$$24$$$.