กำหนดอาร์เรย์ $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, ? เนื่องจากผลลัพธ์ทั้งหมดอาจมีขนาดใหญ่ คุณจึงต้องแสดงผลเพียงค่า 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$