Tveir vinir söfnuðu $n^2$ skeljum á strönd og röðuðu þeim í grind með $n$ röðum og $n$ dálkum. Síðan teiknuðu þeir nokkrar láréttar og nokkrar lóðréttar línur í sandinn, sem skipti ströndinni í svæði með jákvæðum fjölda skelja úr safni þeirra á hverju svæði.

Nú spila vinirnir hinn þekkta leik Nim. Þeir gera til skiptis; í hverjum leik tekur leikmaður jákvæðan fjölda skelja af einu völdu svæði. Leikmaðurinn sem tekur síðustu skeljarnar vinnur.

Vinirnir vita að til að ákvarða hvort fyrri leikmaðurinn eigi vinningstillögu og hvaða leikur sé bestur, þarf að telja fjölda skelja á hverju svæði og reikna bitvíst XOR (bitwise xor) af þessum tölum. Það hljómar eins og mikil vinna. Hjálpaðu þeim!

Inntak

Fyrsta lína inntaksins inniheldur eina heiltölu $n$ ($1 \le n \le 10^6$). Við gerum ráð fyrir að raðirnar séu númeraðar $1$ til $n$, ofan frá og niður. Dálkarnir eru einnig númeraðir $1$ til $n$, frá vinstri til hægri.

Önnur línan inniheldur streng af $n - 1$ tölustöfum 0 eða 1; $i$-ti tölustafurinn ($1 \le i < n$) er 1 ef það er lárétt lína á milli raðar $i$ og raðar $i + 1$.

Þriðja línan inniheldur streng af $n - 1$ tölustöfum 0 eða 1; $i$-ti tölustafurinn ($1 \le i < n$) er 1 ef það er lóðrétt lína á milli dálks $i$ og dálks $i + 1$.

Úttak

Skrifið út eina heiltölu, bitvíst XOR af fjölda skelja á öllum svæðum.

Dæmi

Inntak

4
001
101

Úttak

4

Athugasemd

Það eru sex svæði sem hafa $3, 1, 6, 2, 3, 1$ skeljar hvert um sig. Bitvíst XOR er jafnt og $3 \oplus 1 \oplus 6 \oplus 2 \oplus 3 \oplus 1 = 4$.