Zwei Freunde haben am Strand $n^2$ Muscheln gesammelt und sie in einem Gitter aus $n$ Zeilen und $n$ Spalten angeordnet. Anschließend zeichneten sie einige horizontale und einige vertikale Linien in den Sand, wodurch der Strand in Zonen unterteilt wurde, sodass sich in jeder Zone eine positive Anzahl von Muscheln aus ihrer Sammlung befand.

Nun spielen die Freunde das bekannte Nim-Spiel. Sie ziehen abwechselnd; in jedem Zug nimmt ein Spieler eine positive Anzahl von Muscheln aus einer einzigen beliebigen Zone. Der Spieler, der die letzten Muscheln nimmt, gewinnt.

Die Freunde wissen: Um festzustellen, ob der erste Spieler eine Gewinnstrategie hat und welcher Zug optimal ist, muss man die Anzahl der Muscheln in jeder Zone zählen und das bitweise XOR dieser Zahlen berechnen. Das klingt nach viel Arbeit. Hilf ihnen!

Eingabe

Die erste Zeile der Eingabe enthält eine ganze Zahl $n$ ($1 \le n \le 10^6$). Wir nehmen an, dass die Zeilen von oben nach unten von $1$ bis $n$ nummeriert sind. Die Spalten sind ebenfalls von links nach rechts von $1$ bis $n$ nummeriert.

Die zweite Zeile enthält eine Zeichenkette aus $n - 1$ Ziffern 0 oder 1; die $i$-te Ziffer ($1 \le i < n$) ist 1, wenn sich zwischen Zeile $i$ und Zeile $i + 1$ eine horizontale Linie befindet.

Die dritte Zeile enthält eine Zeichenkette aus $n - 1$ Ziffern 0 oder 1; die $i$-te Ziffer ($1 \le i < n$) ist 1, wenn sich zwischen Spalte $i$ und Spalte $i + 1$ eine vertikale Linie befindet.

Ausgabe

Gib eine einzige ganze Zahl aus: das bitweise XOR der Muschelanzahlen in allen Zonen.

Beispiel

Eingabe

4
001
101

Ausgabe

4

Hinweis

Es gibt sechs Zonen mit jeweils $3, 1, 6, 2, 3, 1$ Muscheln. Das bitweise XOR ist gleich $3 \oplus 1 \oplus 6 \oplus 2 \oplus 3 \oplus 1 = 4$.