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

Дан массив $$$a_1, a_2, \ldots, a_n$$$, состоящий из целых чисел.

Определим операцию «уничтожения» с целочисленным параметром $$$k$$$ ($$$1 \leq k \leq n$$$):

  • Выбрать $$$k$$$ различных индексов массива $$$1 \leq i_1 \lt i_2 \lt \ldots \leq i_k$$$.
  • Вычислить $$$x = a_{i_1} ~ \text{AND} ~ a_{i_2} ~ \text{AND} ~ \ldots ~ \text{AND} ~ a_{i_k}$$$, где $$$\text{AND}$$$ это операция побитового «И» (обратитесь к тексту в конце условия для формального определения).
  • Вычесть $$$x$$$ из всех $$$a_{i_1}, a_{i_2}, \ldots, a_{i_k}$$$ и оставить остальные элементы массива без изменения.

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

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

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

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

В следующей строке находится $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \lt 2^{30}$$$).

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

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

Для каждого набора входных данных выведите все значения $$$k$$$, для которых с помощью операций уничтожения можно сделать все элементы массива равными $$$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\}$$$. При каждой из этих операций число на соответствующем индексе занулится.
  • При $$$k = 2$$$ мы можем сделать две операции уничтожения с наборами индексов $$$\{1, 2\}$$$, $$$\{3, 4\}$$$. При каждой из этих операций числа на соответствующих индексах будут зануляться.
  • При $$$k = 3$$$ невозможно сделать все $$$a_i$$$ равными $$$0$$$. Если мы сделаем любую операцию уничтожения в самом начале, то в нашем массиве три числа станет равными $$$0$$$ и одно число останется равным $$$4$$$. После этого любая операция уничтожения не будет изменять массив, потому что среди индексов, которые используются, будет индекс, значение массива для которого равно $$$0$$$.
  • При $$$k = 4$$$ мы можем сделать одну операцию уничтожения с набором индексов $$$\{1, 2, 3, 4\}$$$.

Во втором наборе входных данных при $$$k = 2$$$ мы можем сделать следующие операции уничтожения:

  • Операция с индексами $$$\{1, 3\}$$$. Из элементов на этих индексах вычитается $$$9 = 13 ~ \text{AND} ~ 25$$$. Массив после операции станет $$$[4, 7, 16, 19]$$$.
  • Операция с индексами $$$\{3, 4\}$$$. Из элементов на этих индексах вычитается $$$16 = 16 ~ \text{AND} ~ 19$$$. Массив после операции станет $$$[4, 7, 0, 3]$$$.
  • Операция с индексами $$$\{2, 4\}$$$. Из элементов на этих индексах вычитается $$$3 = 7 ~ \text{AND} ~ 3$$$. Массив после операции станет $$$[4, 4, 0, 0]$$$.
  • Операция с индексами $$$\{1, 2\}$$$. Из элементов на этих индексах вычитается $$$4 = 4 ~ \text{AND} ~ 4$$$. Массив после операции станет $$$[0, 0, 0, 0]$$$.

Формальное определение побитового «И»

Определим операцию побитового «И» (AND). Пусть даны два целых неотрицательных числа $$$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 ~ \text{AND} ~ y$$$ — результат операции AND над числами $$$x$$$ и $$$y$$$. Тогда двоичной записью $$$r$$$ будет $$$r_k \dots r_2 r_1 r_0$$$, где:

$$$$$$ r_i = \begin{cases} 1, ~ \text{если} ~ x_i = 1 ~ \text{и} ~ y_i = 1 \\ 0, ~ \text{если} ~ x_i = 0 ~ \text{или} ~ y_i = 0 \end{cases} $$$$$$