لدينا مصفوفة $a_0, a_1, \dots, a_{2^n-1}$ طولها $2^n$. بالنسبة لسلسلة نصية $q$ طولها $n$ مكونة من الأبجدية 0، 1، ? (مرقمة بدءاً من 1)، نعرّف «مجموع المجموعة الجزئية المعمم» $S(q)$ بأنه مجموع $a_j$ عبر جميع الفهارس $j$ التي تحقق:

• لكل $1 \le k \le n$، إذا كان $q_k = \texttt{0}$ فإن البت رقم $k$ للعدد $j$ هو $0$.
• لكل $1 \le k \le n$، إذا كان $q_k = \texttt{1}$ فإن البت رقم $k$ للعدد $j$ هو $1$.
• إذا كان $q_k = \texttt{?}$ فلا يوجد أي قيد على البت رقم $k$ للعدد $j$.

على سبيل المثال، عندما $n = 3$ و $q = \texttt{0?1}$، فإن مجموع المجموعة الجزئية المعمم هو $S(q) = a_4 + a_6$ (بالثنائي $\texttt{100}$ و $\texttt{110}$). لاحظ أن البت الأول هو البت الأقل أهمية.

مهمتك هي حساب مجموع المجموعة الجزئية المعمم لكل سلسلة طولها $n$ مكونة من الأبجدية 0، 1، ?. ونظراً لأن الإخراج الكلي قد يكون كبيراً، فإنك تحتاج فقط إلى طباعة ناتج عملية XOR الثنائية (bitwise XOR) لجميع هذه المجاميع.

الإدخال

السطر الأول من الإدخال يحتوي على عدد صحيح $n$ ($1 \le n \le 16$).

السطر الثاني من الإدخال يحتوي على $2^n$ أعداد صحيحة $a_0, a_1, \dots, a_{2^n-1}$ ($0 \le a_i \le 9$)، وهي محتويات المصفوفة $a$.

الإخراج

اطبع عدداً صحيحاً يمثل ناتج bitwise-XOR لجميع مجاميع المجموعات الجزئية المعممة.

أمثلة

مثال الإدخال 1

1
3 5

مثال الإخراج 1

14

مثال الإدخال 2

2
2 6 8 8

مثال الإخراج 2

0

ملاحظة

فيما يلي سلاسل الاستعلام $q$ ومجاميع المجموعات الجزئية المعممة المقابلة لها $S(q)$ في المثال 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$

الآن من السهل التحقق من أن المخرج هو $0$.