Två vänner samlade $n^2$ snäckor på en strand och placerade dem i ett rutnät med $n$ rader och $n$ kolumner. Därefter ritade de några horisontella och några vertikala linjer i sanden, vilket delade in stranden i zoner med ett positivt antal snäckor från deras samling i varje zon.
Nu spelar vännerna det välkända spelet Nim. De gör draget varannan gång; i varje drag tar en spelare ett positivt antal snäckor från en enda valfri zon. Spelaren som tar de sista snäckorna vinner.
Vännerna vet att för att avgöra om den första spelaren har en vinnande strategi, och vilket drag som är optimalt, bör man räkna antalet snäckor i varje zon och beräkna bitvis XOR av dessa tal. Det låter som väldigt mycket arbete. Hjälp dem!
Indata
Den första raden i indatan innehåller ett heltal $n$ ($1 \le n \le 10^6$). Vi antar att raderna är numrerade $1$ till $n$, uppifrån och ned. Kolumnerna är också numrerade $1$ till $n$, från vänster till höger.
Den andra raden innehåller en sträng med $n - 1$ siffror 0 eller 1; den $i$-te siffran ($1 \le i < n$) är 1 om det finns en horisontell linje mellan rad $i$ och rad $i + 1$.
Den tredje raden innehåller en sträng med $n - 1$ siffror 0 eller 1; den $i$-te siffran ($1 \le i < n$) är 1 om det finns en vertikal linje mellan kolumn $i$ och kolumn $i + 1$.
Utdata
Skriv ut ett enda heltal, bitvis XOR av antalet snäckor i alla zoner.
Exempel
Indata
4 001 101
Utdata
4
Förklaring
Det finns sex zoner som har $3, 1, 6, 2, 3, 1$ snäckor vardera. Bitvis XOR är lika med $3 \oplus 1 \oplus 6 \oplus 2 \oplus 3 \oplus 1 = 4$.
