Cho một mảng $a_0, a_1, \dots, a_{2^n-1}$ có độ dài $2^n$. Với một xâu $q$ có độ dài $n$ trên bảng chữ cái 0, 1, ? (đánh số từ 1), định nghĩa "tổng tập con tổng quát" $S(q)$ là tổng của $a_j$ trên tất cả các chỉ số $j$ thỏa mãn:

• Với mỗi $1 \le k \le n$, nếu $q_k = \texttt{0}$ thì bit thứ $k$ của $j$ là $0$.
• Với mỗi $1 \le k \le n$, nếu $q_k = \texttt{1}$ thì bit thứ $k$ của $j$ là $1$.
• Nếu $q_k = \texttt{?}$ thì không có ràng buộc nào đối với bit thứ $k$ của $j$.

Ví dụ, khi $n = 3$ và $q = \texttt{0?1}$, tổng tập con tổng quát là $S(q) = a_4 + a_6$ (biểu diễn nhị phân là $\texttt{100}$ và $\texttt{110}$). Lưu ý rằng bit thứ nhất là bit thấp nhất.

Nhiệm vụ của bạn là tính tổng tập con tổng quát cho mỗi xâu độ dài $n$ trên bảng chữ cái 0, 1, ?. Vì tổng lượng kết quả có thể rất lớn, bạn chỉ cần in ra giá trị XOR theo bit (bitwise XOR) của tất cả các tổng này.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa một số nguyên $n$ ($1 \le n \le 16$).

Dòng thứ hai của dữ liệu vào chứa $2^n$ số nguyên $a_0, a_1, \dots, a_{2^n-1}$ ($0 \le a_i \le 9$), là các phần tử trong mảng $a$.

Kết quả

In ra một số nguyên biểu thị giá trị XOR theo bit của tất cả các tổng tập con tổng quát.

Ví dụ

Dữ liệu vào mẫu 1

1
3 5

Kết quả mẫu 1

14

Dữ liệu vào mẫu 2

2
2 6 8 8

Kết quả mẫu 2

0

Ghi chú

Dưới đây là các xâu truy vấn $q$ và tổng tập con tổng quát $S(q)$ tương ứng trong ví dụ 2:

• $q = \texttt{00}, S(q) = a_0 = 2$
• $q = \texttt{10}, S(q) = a_1 = 6$
• $q = \texttt{?0}, S(q) = a_0 + a_1 = 2 + 6 = 8$
• $q = \texttt{01}, S(q) = a_2 = 8$
• $q = \texttt{11}, S(q) = a_3 = 8$
• $q = \texttt{?1}, S(q) = a_2 + a_3 = 16$
• $q = \texttt{0?}, S(q) = a_0 + a_2 = 10$
• $q = \texttt{1?}, S(q) = a_1 + a_3 = 14$
• $q = \texttt{??}, S(q) = a_0 + a_1 + a_2 + a_3 = 24$

Bây giờ có thể dễ dàng kiểm tra được rằng kết quả là $0$.