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