D. Maximum AND
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a = [a_1, ~a_2, ~\ldots, ~a_n]$$$ of $$$n$$$ integers.

For each integer $$$k$$$ from $$$1$$$ to $$$n$$$, consider the following operation:

  • Choose two indices $$$i$$$ and $$$j$$$ such that $$$|i - j| \ge k$$$.
  • Replace $$$a_i$$$ with the bitwise OR of $$$a_i$$$ and $$$a_j$$$ ($$$a_i | a_j$$$).

You can perform this operation any number of times (possibly zero).

For each $$$k$$$ independently, determine the maximum possible value of the bitwise AND of all elements in the array after performing any number of such operations. That is, for each $$$k$$$ from $$$1$$$ to $$$n$$$, find the maximum achievable value of $$$(a_1 ~\& ~a_2 ~\& ~\ldots ~\& ~a_n)$$$.

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. The description of the test cases follows.

The first line contains an integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of the array $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1, ~a_2, ~\ldots, ~a_n$$$ ($$$1 \le a_i \le 10^9$$$).

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

Output

For each test case, print $$$n$$$ space-separated integers in a new line, where the $$$k$$$-th integer represents the maximum bitwise AND achievable for the given $$$k$$$.

Example
Input
2
10
1 2 3 4 5 6 7 8 9 10
5
2 4 3 5 6
Output
15 15 15 15 15 4 0 0 0 0
7 7 3 0 0