Вам задан массив \(a_1, a_2, \ldots, a_n\), состоящий из неотрицательных целых чисел.
Определим операцию «уничтожения» с целочисленным параметром \(k\) (\(1 \leq k \leq n\)) следующим образом:
- Выбираем \(k\) различных индексов массива \(1 \leq i_1 < i_2 < \ldots < i_k \le n\).
- Вычисляем \(x = a_{i_1} ~ \& ~ a_{i_2} ~ \& ~ \ldots ~ \& ~ a_{i_k}\), где \(\&\) обозначает операцию побитового И (обратитесь к тексту в примечании для формального определения).
- Вычитаем \(x\) из всех \(a_{i_1}, a_{i_2}, \ldots, a_{i_k}\); остальные элементы массива оставляем без изменения.
Найдите все значения \(k\), для которых с помощью конечного количества операций уничтожения с параметром \(k\) можно сделать все элементы массива \(a\) равными \(0\). Можно показать, что для любого массива \(a\) существует хотя бы одно подходящее \(k\).
Обратите внимание, что вы сначала выбираете значение \(k\) и только потом применяете операции уничтожения с первоначально выбранным параметром \(k\).
Выходные данные
Для каждого набора входных данных выведите все значения \(k\), для которых с помощью операций уничтожения (с заданным параметром \(k\)) можно сделать все элементы массива \(a\) равными \(0\).
Выводите их в возрастающем порядке.
Примечание
В первом наборе входных данных:
- При \(k = 1\) мы можем сделать четыре операции уничтожения с наборами индексов \(\{1\}\), \(\{2\}\), \(\{3\}\), \(\{4\}\). Так как \(\&\) одного элемента равен самому элементу, то при каждой операции \(x = a_i\), и \(a_i - x = a_i - a_i = 0\).
- При \(k = 2\) мы можем сделать две операции уничтожения с наборами индексов, например, \(\{1, 3\}\) и \(\{2, 4\}\): \(x = a_1 ~ \& ~ a_3\) \(=\) \(a_2 ~ \& ~ a_4\) \(=\) \(4 ~ \& ~ 4 = 4\). При каждой из этих операций \(x = 4\), а потому после первой операции \(a_1 - x = 0\) и \(a_3 - x = 0\), и после второй — \(a_2 - x = 0\) и \(a_4 - x = 0\).
- При \(k = 3\) невозможно сделать все \(a_i\) равными \(0\). Если мы сделаем любую операцию уничтожения в самом начале, то в нашем массиве три числа станут равными \(0\) и одно число останется равным \(4\). После этого любая операция уничтожения не будет изменять массив, потому что среди выбранных индексов будет хотя бы один, значение массива для которого уже равно \(0\).
- При \(k = 4\) мы можем сделать одну операцию уничтожения с набором индексов \(\{1, 2, 3, 4\}\), потому что \(x = a_1 ~ \& ~ a_2 ~ \& ~ a_3 ~ \& ~ a_4\) \(= 4\).
Во втором наборе входных данных при \(k = 2\) мы можем сделать следующие операции уничтожения:
- Операция с индексами \(\{1, 3\}\): \(x = a_1 ~ \& ~ a_3\) \(=\) \(13 ~ \& ~ 25 = 9\). \(a_1 - x = 13 - 9 = 4\) и \(a_3 - x = 25 - 9 = 16\). Массив \(a\) после операции станет \([4, 7, 16, 19]\).
- Операция с индексами \(\{3, 4\}\): \(x = a_3 ~ \& ~ a_4\) \(=\) \(16 ~ \& ~ 19 = 16\). \(a_3 - x = 16 - 16 = 0\) и \(a_4 - x = 19 - 16 = 3\). Массив \(a\) после операции станет \([4, 7, 0, 3]\).
- Операция с индексами \(\{2, 4\}\): \(x = a_2 ~ \& ~ a_4\) \(=\) \(7 ~ \& ~ 3 = 3\). \(a_2 - x = 7 - 3 = 4\) и \(a_4 - x = 3 - 3 = 0\). Массив \(a\) после операции станет \([4, 4, 0, 0]\).
- Операция с индексами \(\{1, 2\}\): \(x = a_1 ~ \& ~ a_2\) \(=\) \(4 ~ \& ~ 4 = 4\). \(a_1 - x = 4 - 4 = 0\) и \(a_2 - x = 4 - 4 = 0\). Массив \(a\) после операции станет \([0, 0, 0, 0]\).
Формальное определение побитового «И»
Определим операцию побитового «И» (\(\&\)). Пусть даны два целых неотрицательных числа \(x\) и \(y\), рассмотрим их двоичные записи (возможно с ведущими нулями): \(x_k \dots x_2 x_1 x_0\) и \(y_k \dots y_2 y_1 y_0\). Здесь \(x_i\) это \(i\)-й бит числа \(x\), а \(y_i\) это \(i\)-й бит числа \(y\). Пусть \(r = x ~ \& ~ y\) — результат операции \(\&\) над числами \(x\) и \(y\). Тогда двоичной записью \(r\) будет \(r_k \dots r_2 r_1 r_0\), где:
\(\) r_i = \begin{cases} 1, ~ \text{if} ~ x_i = 1 ~ \text{and} ~ y_i = 1 \\ 0, ~ \text{if} ~ x_i = 0 ~ \text{or} ~ y_i = 0 \end{cases} \(\)
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
4
4 4 4 4
4
13 7 25 19
6
3 5 3 1 7 1
1
1
5
0 0 0 0 0
|
1 2 4
1 2
1
1
1 2 3 4 5
|