CF2211D.AND-array

For a sequence $ a $ of length $ n $ , we define its AND-array $ f(a) $ as follows:

$ 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} $

for all $ 1\le k\le n $ , where $ & $ denotes the bitwise AND operation.

In other words, $ f(a)_k $ is a sum of bitwise AND over all subsequences $ ^{\text{∗}} $ of $ a $ with length $ k $ .

The sequence $ a $ is unknown to you. However, you are provided with a sequence $ b $ of length $ n $ such that $ b_i \equiv f(a)_i \pmod{10^9 + 7} $ for all $ 1 \le i \le n $ . Your task is to reconstruct the sequence $ a $ based on the given sequence $ b $ .

$ ^{\text{∗}} $ A sequence $ c $ is a subsequence of a sequence $ d $ if $ c $ can be obtained from $ d $ by the deletion of several (possibly, zero or all) element from arbitrary positions. Two subsequences are considered different if the sets of positions of the deleted elements are different.

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows.

The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 10^5 $ ) — the length of sequences $ a $ and $ b $ .

The second line of each test case contains $ n $ integers $ b_1, b_2, \ldots, b_n $ ( $ 0 \le b_i \lt 10^9 + 7 $ ) — the sequence $ b $ .

It is guaranteed that there exists a sequence $ a $ of length $ n $ with $ 0 \le a_i \lt 2^{29} $ , such that $ b_i \equiv f(a)_i \pmod{10^9 + 7} $ for all $ 1 \le i \le n $ .

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^5 $ .

Output $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 0\le a_i \lt 2^{29} $ ) representing the reconstructed sequence $ a $ . If there are multiple possible sequences satisfying the constraints, output any.

In the second example, for $ a = [5, 3, 6, 1, 7] $ the value of $ f(a)_4 $ is $ 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 $ , and $ f(a)_1 = a_1 + a_2 + a_3 + a_4 + a_5 = 22 $ . It can be proven that $ f(a)_i = b_i $ for all $ 1 \le i \le 5 $ , so $ a = [5, 3, 6, 1, 7] $ is a valid solution.