После окончания университета Влад получил массив \(a_1,a_2,\ldots,a_n\) из \(n\) целых неотрицательных чисел. Он сразу же захотел построить граф, состоящий из \(n\) вершин, пронумерованных \(1, 2,\ldots, n\). Он решил добавлять ребро между \(i\) и \(j\) тогда и только тогда, когда \(a_i \& a_j > 0\), где \(\&\) обозначает операцию побитового И.
Влад также хочет, чтобы такой граф был связным, что, к сожалению, может быть не так. Чтобы удовлетворить свое желание, он может выполнять следующие два типа операций над массивом:
- Выбрать некоторый элемент \(a_i\) и увеличить его на \(1\).
- Выбрать некоторый элемент \(a_i\) и уменьшить его на \(1\) (разрешено, только если \(a_i > 0\)).
Можно доказать, что существует конечная последовательность таких операций, при которой граф станет связным. Не могли бы вы помочь Владу найти минимально возможное количество операций для этого, а также предоставить способ, как это сделать?
Выходные данные
Для каждого набора входных данных выведите в первой строке единственное целое число \(m\) — минимальное количество операций. Во второй строке выведите массив после допустимой последовательности операций, которые были выполнены так, что граф из задачи стал связным.
Если решений несколько, выведите любое.
Примечание
В первом наборе входных данных граф уже связен.
Во втором наборе входных данных мы можем дважды увеличить \(0\) и получить массив \([2,2]\). Поскольку \(2 \& 2 = 2 > 0\), граф связен. Можно показать, что одной операции недостаточно.
В третьем наборе входных данных мы можем один раз уменьшить \(12\) и получить массив \([3,11]\). \(3 \& 11 = 3 > 0\), следовательно, граф связен. Необходимо выполнить одну операцию, так как граф вначале не связен.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
5
1 2 3 4 5
2
0 2
2
3 12
4
3 0 0 0
|
0
1 2 3 4 5
2
2 2
1
3 11
3
3 1 1 1
|