C. Нече(с)тный процесс
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть $$$n$$$ монет номиналами $$$a_1, a_2, \ldots, a_n$$$ и натуральное число $$$k$$$. Также у вас есть мешок, изначально пустой, в который вы можете класть монеты. Вам нужно сделать ровно $$$k$$$ действий. В каждом действии вы берёте одну монету из тех, что у вас остались, и кладёте её в свой мешок. После чего вы эту монету больше не можете брать.

При этом у вас есть кот, который очень любит чётные числа, поэтому каждый раз, когда сумма номиналов монет в вашем мешке оказывается чётной, ваш кот опустошает мешок, то есть утаскивает все монеты в одно только ему известное место, и мешок снова оказывается пустым. Обратите внимание, что мешок опустошается каждый раз, когда в процессе добавления в него монет сумма становится чётной, а не только в самый последний момент.

Назовём вашим счётом сумму номиналов монет в мешке. Ваша задача — сделать $$$k$$$ действий так, чтобы ваш итоговый счёт был максимален. Найдите ответ для всех $$$1 \le k \le n$$$.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

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

Вторая строка каждого набора входных данных содержит $$$n$$$ натуральных чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — номиналы монет.

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

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

Для каждого набора входных данных выведите $$$n$$$ чисел — максимально возможный счёт, которого можно достичь, сделав ровно $$$k$$$ действий, для всех $$$k$$$ от $$$1$$$ до $$$n$$$.

Пример
Входные данные
6
3
1 1 1
3
1 2 3
5
4 1 3 1 2
5
4 2 3 1 3
3
4 1 2
3
4 2 2
Выходные данные
1 0 1 
3 5 0 
3 7 9 7 9 
3 7 9 7 9 
1 5 7 
0 0 0
Примечание

В первом наборе входных данных вам доступны монеты номиналами [$$$1,1,1$$$].

  • $$$k=1$$$: в этом случае сумма номиналов в мешке равна $$$1$$$, независимо от выбранной монеты. Итоговый счёт также равен $$$1$$$.
  • $$$k=2$$$: в этом случае сначала сумма номиналов в мешке равна $$$1$$$ независимо от выбора монеты. При выборе второй монеты сумма будет равна $$$2$$$ независимо от выбора монеты и, таким образом, мешок будет опустошен. Итоговый счёт равен $$$0$$$.
  • $$$k=3$$$: в этом случае при выборе первых двух монет сумма будет равна $$$2$$$ и мешок будет опустошен, после чего сумма равна $$$0$$$. При выборе третьей монеты сумма станет равна $$$1$$$.

Во втором наборе входных данных вам доступны монеты номиналами [$$$1,2,3$$$].

  • $$$k=1$$$: в этом случае при выборе монеты номиналом $$$2$$$ мешок будет опустошен и итоговый счёт будет равен $$$0$$$. При выборе монеты номиналом $$$1$$$ или $$$3$$$ итоговый счёт будет $$$1$$$ и $$$3$$$ соответственно. Максимально возможный итоговый счёт — $$$3$$$.
  • $$$k=2$$$: в этом случае при выборе двух монет $$$1$$$ и $$$3$$$ в любом порядке их сумма будет равна $$$4$$$, после чего мешок будет опустошен и итоговый счёт будет равен $$$0$$$. При выборе же $$$3$$$ как первой монеты, счёт станет равен $$$3$$$. Далее можно выбрать, например, монету $$$2$$$, и итоговый счёт станет равен $$$5$$$.
  • $$$k=3$$$: в этом случае сумма всех монет будет равна $$$6$$$, а так как обнуления не меняют четности набираемой суммы, то итоговый счёт — $$$0$$$.