To venner samlet $n^2$ skjell på en strand og la dem i et rutenett med $n$ rader og $n$ kolonner. Deretter tegnet de noen horisontale og noen vertikale linjer i sanden, noe som delte stranden inn i soner med et positivt antall skjell fra samlingen deres i hver sone.
Nå spiller vennene det velkjente spillet Nim. De trekker annenhver gang; i hvert trekk tar en spiller et positivt antall skjell fra én enkelt valgfri sone. Spilleren som tar de siste skjellene vinner.
Vennene vet at for å avgjøre om den første spilleren har en vinnende strategi, og hvilket trekk som er optimalt, bør man telle antall skjell i hver sone og beregne bitvis XOR av disse tallene. Det høres ut som mye arbeid. Hjelp dem!
Inndata
Den første linjen i inndataene inneholder ett heltall $n$ ($1 \le n \le 10^6$). Vi antar at radene er nummerert $1$ til $n$, ovenfra og ned. Kolonnene er også nummerert $1$ til $n$, fra venstre mot høyre.
Den andre linjen inneholder en streng med $n - 1$ sifre 0 eller 1; det $i$-te sifferet ($1 \le i < n$) er 1 hvis det er en horisontal linje mellom rad $i$ og rad $i + 1$.
Den tredje linjen inneholder en streng med $n - 1$ sifre 0 eller 1; det $i$-te sifferet ($1 \le i < n$) er 1 hvis det er en vertikal linje mellom kolonne $i$ og kolonne $i + 1$.
Utdata
Skriv ut ett enkelt heltall, bitvis XOR av antall skjell i alle sonene.
Eksempel
Inndata
4 001 101
Utdata
4
Forklaring
Det er seks soner som har henholdsvis $3, 1, 6, 2, 3, 1$ skjell. Bitvis XOR er lik $3 \oplus 1 \oplus 6 \oplus 2 \oplus 3 \oplus 1 = 4$.
