给定数组 $$$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}$$$,其中 $$$\&$$$ 表示按位 AND 运算(注释部分包含正式定义)。
- 从 $$$a_{i_1}, a_{i_2}, \ldots, a_{i_k}$$$ 中减去 $$$x$$$;所有其他元素保持不变。
找到 $$$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$$$。
按升序打印它们。
示例
输入 #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
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]$$$。
按位与的正式定义:
让我们定义按位 AND ($$$\&$$$) 如下。假设我们有两个非负整数 $$$x$$$ 和 $$$y$$$,让我们看看它们的二进制表示形式(可能带有前导零):$$$x_k \dots x_2 x_1 x_0$$$ 和 $$$y_k \dots y_2 y_1 y_0$$$。这里,$$$x_i$$$是数字$$$x$$$的第$$$i$$$位,$$$y_i$$$是数字$$$y$$$的第$$$i$$$位。设 $$$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} $$$$$$