У Маши и Оли скоро важная командная олимпиада. В честь этого Маша, для разминки, предложила сыграть Оле в следующую игру:
Есть массив \(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\). Какое число тогда останется при оптимальной игре обоих игроков?
Выходные данные
Для каждого набора входных данных выведите \(n\) целых чисел. \(k\)-е из этих чисел должно быть равно числу, которое останется в конце при оптимальной игре обоих, на массиве, состоящем из первых \(k\) элементов массива \(a\).
Примечание
В третьем наборе входных данных для префикса длины \(1\) ответ \(3\). Для префикса длины \(2\) у Маши есть один вариант для хода, поэтому ответ \(12\). Для префикса длины \(3\) у Маши есть три возможных хода: она выбирает \(3\) и \(10\), тогда число в конце \(22\), \(3\) и \(11\), тогда число в конце \(24\), \(10\) и \(11\), тогда число в конце \(22\), значит Маша выберет \(3\) и \(11\) и получит \(24\).