Екі дос жағажайда $n^2$ бақалшақ жинап, оларды $n$ жол мен $n$ бағаннан тұратын тор түрінде орналастырды. Содан кейін олар құм бетіне бірнеше көлденең және тік сызықтар сызып, жағажайды аймақтарға бөлді; әр аймақта олардың жинағынан оң сандағы бақалшақтар қалды.
Енді достар әйгілі Ним (Nim) ойынын ойнайды. Олар кезекпен жүріс жасайды; әр жүрісте ойыншы кез келген бір аймақтан оң сандағы бақалшақтарды алады. Соңғы бақалшақтарды алған ойыншы жеңеді.
Достар бірінші ойыншыда жеңіс стратегиясы бар-жоғын және қай жүріс тиімді екенін анықтау үшін әр аймақтағы бақалшақтар санын есептеп, осы сандардың биттік XOR (bitwise xor) мәнін табу керектігін біледі. Бұл өте көп жұмыс сияқты естіледі. Оларға көмектесіңіз!
Кіріс деректер
Кірістің бірінші жолында бір бүтін сан $n$ ($1 \le n \le 10^6$) берілген. Жолдар жоғарыдан төмен қарай $1$-ден $n$-ге дейін нөмірленген деп есептейміз. Бағандар да солдан оңға қарай $1$-ден $n$-ге дейін нөмірленген.
Екінші жолда 0 немесе 1 цифрларынан тұратын ұзындығы $n - 1$ жол берілген; егер $i$-ші жол мен $i + 1$-ші жолдың арасында көлденең сызық болса, $i$-ші цифр ($1 \le i < n$) 1 болады.
Үшінші жолда 0 немесе 1 цифрларынан тұратын ұзындығы $n - 1$ жол берілген; егер $i$-ші баған мен $i + 1$-ші бағанның арасында тік сызық болса, $i$-ші цифр ($1 \le i < n$) 1 болады.
Шығыс деректер
Барлық аймақтардағы бақалшақтар санының биттік XOR мәні болатын жалғыз бүтін санды шығарыңыз.
Мысал
Кіріс
4 001 101
Шығыс
4
Ескертпе
Сәйкесінше $3, 1, 6, 2, 3, 1$ бақалшағы бар алты аймақ бар. Биттік XOR мәні $3 \oplus 1 \oplus 6 \oplus 2 \oplus 3 \oplus 1 = 4$-ке тең.
