Mixed-up Readings#13073

Mixed-up Readings

3 seconds
256 megabytes

The old alchemist Orest keeps a collection of magic crystals; the -th crystal has a positive integer charge a_i. Charges of different crystals may coincide.

Orest has two devices. If you place a non-empty group of crystals on the scale, it will show the total charge of the group, that is, the sum of the charges. If you place the same group on the resonator, it will show the bitwise OR of their charges.

One night Orest measured each of the 2^n - 1 non-empty groups of crystals on both devices and recorded all the readings in a log. Thus, the log contains exactly 2 \cdot (2^n - 1) numbers. Unfortunately, the records were on separate sheets of paper that got mixed up: now it is unknown which group each reading belongs to and which device produced it. The crystals themselves have already been sold.

Given the 2 \cdot (2^n - 1) readings in an arbitrary order, recover the charges of the crystals.

Formally, for an array a_1, a_2, \ldots, a_n and a non-empty set of indices S \subseteq \{1, \ldots, n\} denote \mathrm{sum}(S) = \sum_{i \in S} a_i and \mathrm{or}(S) = a_{i_1} \mathbin{|} a_{i_2} \mathbin{|} \ldots \mathbin{|} a_{i_k}, where S = \{i_1, \ldots, i_k\}, and is the bitwise OR. The log is a multiset consisting of the numbers and for all 2^n - 1 non-empty sets (if \mathrm{sum}(S) = \mathrm{or}(S), then for this that value appears twice).

Input

The first line contains a single integer (1 \le t \le 10^5) — the number of test cases.

Each test case consists of two lines. The first line contains an integer (1 \le n \le 20) — the number of crystals. The second line contains 2 \cdot (2^n - 1) integers b_1, b_2, \ldots, b_{2 (2^n - 1)} (1 \le b_j \le 2 \cdot 10^{10}) — the readings from the log in an arbitrary order.

It is guaranteed that the readings of each test case are exactly the log of some array of integers a_1, \ldots, a_n, where 1 \le a_i \le 10^9.

The sum of 2^n over all test cases does not exceed 2^{20}.

Output

For each test case, output on a separate line integers a_1, a_2, \ldots, a_n (1 \le a_i \le 10^9) in arbitrary order such that the log of this array matches the given readings as a multiset. If there are multiple answers, output any of them.

Examples

Example 1

Loading
Loading

Note

In the first test case, the only crystal has charge : both devices show .

In the second test case, the charges are and : the scale shows , , , and the resonator shows , , .

In the third test case, both crystals have charge : the scale shows , , , and the resonator shows , , .

In the fourth test case, the charges are , , . The scale shows , , , , , , , and the resonator shows , , , , , , .