Problem Description

Just turned elementary school student N learned about exclusive OR (XOR) in class.

The exclusive OR, for example, when the exclusive OR of non-negative integers $ P $ and $ Q $ is $ R $, is defined as follows:

• The value of the $ 2^k $ ($ 0 ≦ k $, $ k $ is an integer) digit in the binary representation of $ R $ is $ 0 $ if the $ 2^k $ digit in the binary representation of $ P $ is equal to the $ 2^k $ digit in the binary representation of $ Q $, and $ 1 $ otherwise.

Specifically, the exclusive OR value of $ 3 $ and $ 5 $ is $ 6 $ because the binary representation of $ 3 $ is $ 011 $, the binary representation of $ 5 $ is $ 101 $, and thus the binary representation of the exclusive OR is $ 110 $.

Excited about the wonder of exclusive OR, the sister replaced all the non-negative integer values around her with their exclusive OR values.

However, among them was a document that her brother was supposed to submit!

Since her brother is out, she decided to restore the original sequence while she can. As a clue, the following is known:

• The document originally contained $ L $ non-negative integers $ A_1 $, $ A_2 $, ..., $ A_L $. These numbers are no longer written on the document. The sister's goal is to find these numbers.
• The document contains $ L $ non-negative integers $ B_1 $, $ B_2 $, ..., $ B_L $. These numbers are still written on the document and can be known.

The $ B_1 $, $ B_2 $, ..., $ B_L $ are defined as follows:

• For an integer $ i $ ($ 1 ≦ i ≦ L-1 $), $ B_i $ is equal to the exclusive OR of $ A_i $ and $ A_{i+1} $.
• $ B_L $ is equal to the exclusive OR of $ A_L $ and $ A_1 $.

Unfortunately, in some cases, there may be no corresponding original sequence or multiple possible sequences. What should we do?

In distress, the sister remembered that today's lucky item in her fortune-telling was a dictionary. Dictionary, jisho, lexicographical order...

Ultimately, she decided to add the following rules:

• If there is no corresponding original sequence, output -1.
• If there are multiple corresponding original sequences, output the lexicographically smallest sequence.

For two sequences $ S_1 $, $ S_2 $, ..., $ S_L $ and $ T_1 $, $ T_2 $, ..., $ T_L $, $ S_1 $, $ S_2 $, ..., $ S_L $ is lexicographically smaller than $ T_1 $, $ T_2 $, ..., $ T_L $ if there exists an integer $ i $ ($ 1 ≦ i ≦ L $) such that for every integer $ j $ ($ 1 ≦ j ≦ i-1 $), $ S_j = T_j $ and $ S_i < T_i $.

Please create a program that outputs the sequence satisfying the above conditions on behalf of the sister.

Input Format

The input is given from the standard input in the following format:

$ L $ $ B_1 $ $ B_2 $ : $ B_L $

• The first line contains an integer $ L $ ($ 2 ≦ L ≦ 10^5 $), representing the number of digits written on the document.
• The next $ L $ lines contain the non-negative integers left on the document. The $ i $-th line contains an integer $ B_i $ ($ 0 ≦ B_i < 2^{31} $).

Output Format

If there exists a possible original sequence of non-negative integers $ A_1 $, $ A_2 $, ..., $ A_L $, output the lexicographically smallest one in $ L $ lines. The $ i $-th line should contain the integer $ A_i $. If no such sequence exists, output -1. End each output with a newline.

Sample Input and Output

Sample Input #1

2
1
1

Sample Output #1

0
1

Sample Input #2

3
1
4
1

Sample Output #2

-1

Sample Input #3

3
1
2
3

Sample Output #3

0
1
3

Notes/Hints

Sample Explanation 1

The correct answer is the pair of numbers whose exclusive OR is $ 1 $. There are multiple such pairs, but the pair $ A_1 = 0 $, $ A_2 = 1 $ is lexicographically smallest.

Sample Explanation 2

There is no original sequence that satisfies the conditions. Probably, a wrong operation was performed somewhere.

见题面 Input 部分

见题面 Output 部分