J. Mario Kart Bitwise Bash (Green)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

As you race along the track, represented by an array $$$a$$$ of $$$n$$$ integers, each element $$$a[i]$$$ signifies a power-up available at position $$$i$$$. These power-ups have special bitwise properties.

For each possible range size $$$k$$$, from $$$1$$$ to $$$n$$$, a temporary array $$$b$$$ is created to evaluate the potential of power-ups.

Mario Bashing.

For each position $$$i$$$ on the track (from $$$1$$$ to $$$n$$$), the power-up at $$$b[i]$$$ is the bitwise OR of all power-ups $$$a[j]$$$ such that the absolute difference between your current position $$$i$$$ and the power-up's position $$$j$$$ is less than $$$k$$$.

Formally, for a given $$$k$$$: $$$$$$b[i] = \text{OR}_{1 \le j \le n, |i - j| \lt k} (a[j])$$$$$$

Your goal is to determine, for each value of $$$k$$$ from 1 to $$$n$$$, the bitwise AND of all elements in the array $$$b$$$.

Input

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of positions on the track.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_{n}$$$ ($$$0 \le a_i \lt 2^{30}$$$) — representing the power-ups at each position.

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

Output

Output $$$n$$$ integers, where the $$$k$$$-th integer is the bitwise AND of array $$$b$$$ for each $$$k$$$.

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