Cho số nguyên dương ~n~ và dãy số nguyên không âm ~a_1,a_2,...,a_n~. Ta định nghĩa khoảng cách giữa hai số ~x~ và ~y~ là số lần ít nhất phải thực hiện các thao tác sau để biến ~x~ thành ~y~:

• Chọn một lũy thừa của ~2~, kí hiệu là ~2^z~.

• Thực hiện phép gán ~x = x~ ~\oplus~ ~2^z~

Trong đó ~\oplus~ là phép toán ~XOR~ được cho bởi bảng giới đây:

Việc thực hiện phép ~XOR~ trên hai số nguyên là thực hiện phép ~XOR~ trên từng bit trong biểu diễn nhị phân của hai số.

Yêu cầu: Với mỗi số ~a_1,a_2,...,a_n~; hãy tìm một số khác trong dãy có khoảng cách tới số đó là bé nhất.

Input

Vào từ file văn bản mind.inp:

• Dòng đầu tiên chứa số nguyên dương ~n~ (~2\le n \le 5 \times 10^5~) là số phần tử của dãy.

• Dòng thứ hai chứa ~n~ số nguyên không âm ~a_1,a_2,...,a_n~ (~a_i \le 5 \times 10^5~) mô tả dãy được cho.

Output

Đưa ra file văn bản mind.out:

• ~n~ số nguyên, mỗi số nguyên là khoảng cách gần nhất ứng với một phần tử trong phương án tối ưu tìm được.

Scoring

Sample Input 1

6
1 2 4 3 8 15

Sample Output 1

1 1 2 1 2 2