У Александры есть массив \(a\) четной длины, состоящий из чисел \(0\) и \(1\). Элементы массива пронумерованы от \(1\) до \(n\). Она хочет удалить из него не более \(\frac{n}{2}\) элементов (где \(n\) — его длина) таким образом, чтобы знакопеременная сумма массива была равна \(0\) (т.е. \(a_1 - a_2 + a_3 - a_4 + \dotsc = 0\)). Иными словами, Александра хочет, чтобы сумма всех элементов на нечетных позициях была равна сумме всех элементов на четных позициях. Элементы, которые вы удаляете, не обязаны быть последовательными.
К примеру, если у нее был массив \(a = [1, 0, 1, 0, 0, 0]\), и она удалила \(2\)-й и \(4\)-й элементы, то \(a\) станет равным \([1, 1, 0, 0]\) и его знакопеременная сумма будет равна \(1 - 1 + 0 - 0 = 0\).
Помогите ей!
Выходные данные
Для каждого набора входных данных сначала выведите число \(k\) (\(\frac{n}{2} \leq k \leq n\)) — число элементов, которые останутся после удаления. В следующей строке выведите \(k\) чисел, которые не будут удалены, в том порядке, в котором они идут в массиве \(a\). Обратите внимание, вам надо вывести сами числа, а не их индексы.
Можно показать, что ответ всегда существует. Если существует несколько ответов, выведите любой из них.
Примечание
В первом и втором наборах входных данных знакопеременная сумма массива, очевидно, равна \(0\).
В третьем наборе входных данных знакопеременная сумма массива равна \(1 - 1 = 0\).
В четвертом наборе входных данных знакопеременная сумма уже равна \(1 - 1 + 0 - 0 = 0\), мы можем ничего не удалять.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2
1 0
2
0 0
4
0 1 1 1
4
1 1 0 0
|
1
0
1
0
2
1 1
4
1 1 0 0
|