נתון מערך $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}$). שימו לב שהביט הראשון הוא הביט הפחות משמעותי (lowest bit).

המשימה שלכם היא לחשב את סכום תת-הקבוצה המוכלל עבור כל מחרוזת באורך $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$.