Bạn được cho một dãy số $a$ gồm $n$ phần tử. Dãy số $b$ được tạo bằng cách như sau:

• $b_1=a_1\oplus a_2$
• $b_2=a_2\oplus a_3$
• $b_3=a_3\oplus a_4$
• $\dots$
• $b_{n-1}=a_{n-1}\oplus a_n$
• $b_n=a_n\oplus a_1$

Trong đó, $\oplus$ là thao tác bit $XOR$. Bạn có thể đọc tại đây

Bạn được cho dãy số $b$, nhiệm vụ của bạn là tìm một dãy số $a$ thỏa mãn điều kiện sao cho thứ tự từ điển của dãy là nhỏ nhất.

Một dãy số $a$ được coi là có thứ tự từ điển nhỏ hơn dãy số $b$ khi tồn tại vị trí $i$ mà:

• Với mọi vị trí $j<i$ thì $a_j=b_j$
• $a_i<b_i$

3
3
1 2 3
3
1 0 0
10
3 6 4 5 2 4 5 14 1 8

0 1 3
-1
0 3 5 1 4 6 2 7 9 8