A. Уничтожение массива
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задан массив $$$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$$$.

Входные данные

Во входных данных находятся несколько наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следуют сами наборы входных данных.

В первой строке каждого набора задано одно целое число $$$n$$$ ($$$1 \leq n \leq 200\,000$$$) — длина массива $$$a$$$.

В следующей строке каждого набора задано $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i < 2^{30}$$$) — массив $$$a$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$200\,000$$$.

Выходные данные

Для каждого набора входных данных выведите все значения $$$k$$$, для которых с помощью операций уничтожения (с заданным параметром $$$k$$$) можно сделать все элементы массива $$$a$$$ равными $$$0$$$.

Выводите их в возрастающем порядке.

Пример
Входные данные
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
Примечание

В первом наборе входных данных:

  • При $$$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} $$$$$$