D. И-массив
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для последовательности $$$a$$$ длины $$$n$$$ определим её И-массив $$$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$$$, где $$$\&$$$ обозначает операцию побитового И.

Другими словами, $$$f(a)_k$$$ — это сумма значений побитового И по всем подпоследовательностям$$$^{\text{∗}}$$$ последовательности $$$a$$$ длины $$$k$$$.

Последовательность $$$a$$$ вам неизвестна. Однако вам дана последовательность $$$b$$$ длины $$$n$$$ такая, что $$$b_i \equiv f(a)_i \pmod{10^9 + 7}$$$ для всех $$$1 \le i \le n$$$. Ваша задача — восстановить последовательность $$$a$$$ по заданной последовательности $$$b$$$.

$$$^{\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$$$.

Гарантируется, что существует последовательность $$$a$$$ длины $$$n$$$, где $$$0 \le a_i \lt 2^{29}$$$, такая, что $$$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$$$. Если существует несколько подходящих последовательностей, выведите любую.

Пример
Входные данные
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
Примечание

Во втором примере для $$$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$$$. Можно доказать, что $$$f(a)_i = b_i$$$ для всех $$$1 \le i \le 5$$$, поэтому $$$a = [5, 3, 6, 1, 7]$$$ является корректным решением.