Kaksi ystävää keräsi rannalta $n^2$ simpukankuorta ja järjesti ne $n$ rivin ja $n$ sarakkeen ruudukkoon. Sen jälkeen he piirsivät hiekkaan vaakasuoria ja pystysuoria viivoja, jotka jakoivat rannan vyöhykkeisiin siten, että jokaisella vyöhykkeellä oli positiivinen määrä simpukankuoria heidän kokoelmastaan.
Nyt ystävät pelaavat tunnettua Nim-peliä. He tekevät siirtoja vuorotellen; jokaisella siirrolla pelaaja ottaa positiivisen määrän simpukankuoria mistä tahansa yksittäisestä vyöhykkeestä. Viimeiset simpukankuoret ottava pelaaja voittaa.
Ystävät tietävät, että selvittääkseen, onko ensimmäisellä pelaajalla voittostrategia ja mikä siirto on optimaalinen, täytyy laskea simpukankuorten määrä jokaisella vyöhykkeellä ja laskea näiden lukujen bittittäinen XOR. Se kuulostaa kovalta työltä. Auta heitä!
Syöte
Syötteen ensimmäinen rivi sisältää yhden kokonaisluvun $n$ ($1 \le n \le 10^6$). Oletamme, että rivit on numeroitu $1$:stä $n$:ään ylhäältä alas. Sarakkeet on myös numeroitu $1$:stä $n$:ään vasemmalta oikealle.
Toinen rivi sisältää $n - 1$ numeron 0 tai 1 merkkijonon; $i$:s numero ($1 \le i < n$) on 1, jos rivin $i$ ja rivin $i + 1$ välissä on vaakasuora viiva.
Kolmas rivi sisältää $n - 1$ numeron 0 tai 1 merkkijonon; $i$:s numero ($1 \le i < n$) on 1, jos sarakkeen $i$ ja sarakkeen $i + 1$ välissä on pystysuora viiva.
Tuloste
Tulosta yksi kokonaisluku, kaikkien vyöhykkeiden simpukankuorten lukumäärien bittittäinen XOR.
Esimerkki
Syöte
4 001 101
Tuloste
4
Huomautus
Vyöhykkeitä on kuusi, ja niissä on $3, 1, 6, 2, 3, 1$ simpukankuorta. Bittittäinen XOR on $3 \oplus 1 \oplus 6 \oplus 2 \oplus 3 \oplus 1 = 4$.
