Maximum Bitwise OR by Window Length

Time limit2sMemory limit512 MB

Summary

For each window length K from 1 to N, output the maximum bitwise OR over all K consecutive elements of the array.

Level: Hard8 of 10
Topics: Bit manipulation, Divide and conquer, Array, Segment tree
Solved: No attempts yet

Problem

You are given an array of $N$ nonnegative integers. For every integer $K$ between $1$ and $N$ , find the largest value that the bitwise OR of $K$ consecutive elements of the array can take.

The bitwise OR of several nonnegative integers is the integer whose $i$ -th binary digit from the right is $0$ exactly when the $i$ -th binary digit from the right of every one of those integers is $0$ .

Input

The first line contains the length of the array $N$ ( $1 \le N \le 500000$ ).

Each of the next $N$ lines contains one element of the array, an integer $x$ ( $0 \le x < 2^{30}$ ).

Output

Print $N$ lines. On the $k$ -th line, print the largest value that the bitwise OR of $k$ consecutive elements of the array can take.

Examples2

Example 1

Input

Expected output

Example 2
Input
```
5
1
2
4
8
16
```
Expected output
```
16
24
28
30
31
```