对于长度为 $$$n$$$ 的序列 $$$a$$$,我们定义其 AND 数组 $$$f(a)$$$如下:
$$f(a)_k = \sum\limits_{1 \le i_1 \lt i_2 \lt \ldots \lt i_k \le n} a_{i_1} \& a_{i_2} \& \ldots \& a_{i_k}$$
对于所有 $$$1\le k\le n$$$,其中 $$$\&$$$ 表示按位 AND 运算。
换句话说,$$$f(a)_k$$$ 是 $$$a$$$ 长度为 $$$k$$$ 的所有子序列 $$$^{\text{∗}}$$$ 按位 AND 的总和。
您不知道序列$$$a$$$。但是,您会获得长度为 $$$n$$$ 的序列 $$$b$$$,使得对于所有 $$$1 \le i \le n$$$,$$$b_i \equiv f(a)_i \pmod{10^9 + 7}$$$。你的任务是根据给定的序列$$$b$$$重建序列$$$a$$$。
$$$^{\text{*}}$$$ 序列 $$$c$$$ 是序列 $$$d$$$ 的子序列,如果 $$$c$$$ 可以通过从任意位置删除几个(可能是零个或全部)元素从 $$$d$$$ 获得。如果两个子序列的集合被认为是不同的 职位 删除的元素的 不同。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 序列 $$$a$$$ 和 $$$b$$$ 的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$0 \le b_i \lt 10^9 + 7$$$) — 序列 $$$b$$$。
保证存在长度为 $$$n$$$ 且 $$$0 \le a_i \lt 2^{29}$$$ 的序列 $$$a$$$,使得 $$$b_i \equiv f(a)_i \pmod{10^9 + 7}$$$ 对于所有 $$$1 \le i \le n$$$。
保证所有测试用例的$$$n$$$总和不超过$$$10^5$$$。
输出
输出 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0\le a_i \lt 2^{29}$$$) 表示重构序列 $$$a$$$。如果有多个可能的序列满足约束,则输出任意一个。
示例
输入复制
330 0 0522 24 10 1 010130 585 1560 2730 3276 2730 1560 585 130 13
输出复制
0 0 0 5 3 6 1 7 13 13 13 13 13 13 13 13 13 13
注意
在第二个示例中,对于 $$$a = [5, 3, 6, 1, 7]$$$,$$$f(a)_4$$$ 的值为 $$$a_1 \& a_2 \& a_3 \& a_4 + a_1 \& a_2 \& a_3 \& a_5 + a_1 \& a_2 \& a_4 \& a_5 + a_1 \& a_3 \& a_4 \& a_5 + a_2 \& a_3 \& a_4 \& a_5 = 0 + 0 + 1 + 0 + 0 = 1$$$,$$$f(a)_1 = a_1 + a_2 + a_3 + a_4 + a_5 = 22$$$。可以证明,对于所有$$$1 \le i \le 5$$$,$$$f(a)_i = b_i$$$,因此$$$a = [5, 3, 6, 1, 7]$$$是一个有效的解。