เพื่อนสองคนเก็บเปลือกหอยได้ $n^2$ ชิ้นที่ชายหาด และจัดเรียงเป็นตารางขนาด $n$ แถว และ $n$ คอลัมน์ จากนั้นพวกเขาวาดเส้นแนวนอนและเส้นแนวตั้งบางเส้นลงบนผืนทราย ซึ่งแบ่งชายหาดออกเป็นโซน ๆ โดยมีเปลือกหอยจำนวนเต็มบวกอยู่ในแต่ละโซน
ตอนนี้เพื่อนทั้งสองเล่นเกม Nim อันโด่งดัง พวกเขาผลัดกันเดินหมาก ในแต่ละตา ผู้เล่นจะหยิบเปลือกหอยจำนวนเต็มบวกออกจากโซนใดโซนหนึ่งเพียงโซนเดียว ผู้เล่นที่หยิบเปลือกหอยชิ้นสุดท้ายจะเป็นผู้ชนะ
เพื่อนทั้งสองรู้ว่าในการพิจารณาว่าผู้เล่นคนแรกมีกลยุทธ์ที่ชนะแน่นอนหรือไม่ และตาเดินใดเหมาะสมที่สุด จะต้องนับจำนวนเปลือกหอยในทุกโซนและคำนวณค่า bitwise xor ของจำนวนเหล่านี้ ซึ่งฟังดูเหมือนเป็นงานหนักมาก ช่วยพวกเขาที!
ข้อมูลนำเข้า
บรรทัดแรกของข้อมูลนำเข้ามีจำนวนเต็มหนึ่งจำนวนคือ $n$ ($1 \le n \le 10^6$) เราสมมติว่าแถวมีหมายเลข $1$ ถึง $n$ จากบนลงล่าง และคอลัมน์ก็มีหมายเลข $1$ ถึง $n$ จากซ้ายไปขวา
บรรทัดที่สองประกอบด้วยสตริงของตัวเลข 0 หรือ 1 จำนวน $n - 1$ ตัว ตัวเลขตัวที่ $i$ ($1 \le i < n$) จะเป็น 1 หากมีเส้นแนวนอนคั่นระหว่างแถวที่ $i$ และแถวที่ $i + 1$
บรรทัดที่สามประกอบด้วยสตริงของตัวเลข 0 หรือ 1 จำนวน $n - 1$ ตัว ตัวเลขตัวที่ $i$ ($1 \le i < n$) จะเป็น 1 หากมีเส้นแนวตั้งคั่นระหว่างคอลัมน์ที่ $i$ และคอลัมน์ที่ $i + 1$
ข้อมูลส่งออก
แสดงผลจำนวนเต็มเพียงตัวเดียว คือค่า bitwise xor ของจำนวนเปลือกหอยในทุกโซน
ตัวอย่าง
ข้อมูลนำเข้า
4 001 101
ข้อมูลส่งออก
4
หมายเหตุ
มีทั้งหมดหกโซน ซึ่งมีเปลือกหอย $3, 1, 6, 2, 3, 1$ ชิ้นตามลำดับ ค่า bitwise xor เท่ากับ $3 \oplus 1 \oplus 6 \oplus 2 \oplus 3 \oplus 1 = 4$
