Вам дан массив \(a\) из \(n\) целых чисел.
За одну операцию вы можете выполнить следующее двухэтапное действие:
- Выбрать целое число \(x\) (\(0 \le x \le 10^{9}\)).
- Заменить каждое \(a_i\) на \(|a_i - x|\), где \(|v|\) обозначает модуль \(v\).
Например, при выборе \(x = 8\) массив \([5, 7, 10]\) изменится на \([|5-8|, |7-8|, |10-8|] = [3,1,2]\).
Постройте последовательность операций, чтобы сделать все элементы \(a\) равными \(0\) не более чем за \(40\) операций или определите, что это невозможно. Вам не нужно минимизировать количество операций.
Выходные данные
Для каждого набора входных данных выведите одно целое число \(-1\), если невозможно сделать все элементы массива равными \(0\) не более чем за \(40\) операций.
В противном случае выведите две строки. Первая строка должна содержать одно целое число \(k\) (\(0 \le k \le 40\)) — количество операций. Вторая строка должна содержать \(k\) целых чисел \(x_1, x_2, \ldots, x_k\) (\(0 \le x_i \le 10^{9}\)) — последовательность операций, обозначающую, что на \(i\)-й операции вы выбрали \(x=x_i\).
Если существует несколько решений, выведите любое из них.
Вам не обязательно минимизировать количество операций.
Примечание
В первом наборе входных данных мы можем получить нужный массив за одну операцию, выбрав \(x = 5\) и изменив массив с \([5]\) на \([0]\).
Во втором наборе входных данных никаких операций не требуется, поскольку все элементы массива уже равны \(0\).
В третьем наборе входных данных мы можем выбрать \(x = 6\), чтобы изменить массив с \([4, 6, 8]\) на \([2, 0, 2]\), затем выбрать \(x = 1\), чтобы изменить его на \([1, 1, 1]\), и, наконец, снова выбрать \(x = 1\), чтобы изменить массив на \([0, 0, 0]\).
В четвертом наборе входных данных мы можем сделать все элементы равными \(0\), выполнив последовательность операций \((60, 40, 20, 10, 30, 25, 5)\).
В пятом наборе входных данных можно показать, что невозможно сделать все элементы равными \(0\) не более чем за \(40\) операций. Поэтому ответом будет \(-1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1
5
2
0 0
3
4 6 8
4
80 40 20 10
5
1 2 3 4 5
|
1
5
0
3
6 1 1
7
60 40 20 10 30 25 5
-1
|