题目描述

对于一个长度为 $n$ 的序列 $a$，我们定义它的 AND 数组 $f(a)$ 如下：

$$f(a)_k = \sum_{1 \le i_1 < i_2 < \dots < i_k \le n} a_{i_1} \mathbin{\&} a_{i_2} \mathbin{\&} \dots \mathbin{\&} a_{i_k}$$

对所有 $1 \le k \le n$，其中 $\mathbin{\&}$ 表示按位与运算。

换句话说，$f(a)_k$ 是 $a$ 中所有长度为 $k$ 的子序列的按位与之和。

序列 $a$ 是未知的。但给你一个长度为 $n$ 的序列 $b$，满足对所有 $1 \le i \le n$：

$$b_i \equiv f(a)_i \pmod{10^9 + 7}$$

请你根据 $b$ 还原出序列 $a$。

输入格式

第一行一个整数 $t$，表示测试用例个数。

每个测试用例：

第一行一个整数 $n$，表示序列长度。

第二行 $n$ 个整数 $b_1, b_2, \dots, b_n$。

输出格式

对于每个测试用例，输出一行 $n$ 个整数 $a_1, a_2, \dots, a_n$。 如果有多个合法答案，输出任意一个即可。

3
3
0 0 0
5
22 24 10 1 0
10
130 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

数据规模与约定

$1 \le t \le 10^4$

$1 \le n \le 10^5$

$0 \le b_i < 10^9 + 7$

$0 \le a_i < 2^{29}$

所有测试用例的 $n$ 之和不超过 $10^5$。

保证一定存在合法解。

来源：Codeforces Round 1088 (Div. 1 + Div. 2)

题目网址：https://codeforces.com/contest/2211/problem/D