Deux amis ont ramassé $n^2$ coquillages sur une plage et les ont disposés en une grille de $n$ lignes et $n$ colonnes. Ils ont ensuite tracé des lignes horizontales et verticales dans le sable, ce qui a divisé la plage en zones contenant chacune un nombre strictement positif de coquillages de leur collection.
Maintenant, les amis jouent au célèbre jeu de Nim. Ils jouent à tour de rôle ; à chaque coup, un joueur prend un nombre strictement positif de coquillages dans une seule zone quelconque. Le joueur qui prend les derniers coquillages gagne.
Les amis savent que pour déterminer si le premier joueur a une stratégie gagnante et quel coup est optimal, il faut compter le nombre de coquillages dans chaque zone et calculer le OU exclusif bit à bit (XOR) de ces nombres. Cela semble représenter beaucoup de travail. Aidez-les !
Entrée
La première ligne de l'entrée contient un entier $n$ ($1 \le n \le 10^6$). Nous supposons que les lignes sont numérotées de $1$ à $n$, de haut en bas. Les colonnes sont également numérotées de $1$ à $n$, de gauche à droite.
La deuxième ligne contient une chaîne de $n - 1$ chiffres 0 ou 1 ; le $i$-ème chiffre ($1 \le i < n$) vaut 1 s'il y a une ligne horizontale entre la ligne $i$ et la ligne $i + 1$.
La troisième ligne contient une chaîne de $n - 1$ chiffres 0 ou 1 ; le $i$-ème chiffre ($1 \le i < n$) vaut 1 s'il y a une ligne verticale entre la colonne $i$ et la colonne $i + 1$.
Sortie
Affichez un seul entier, le OU exclusif bit à bit des nombres de coquillages dans toutes les zones.
Exemple
Entrée
4 001 101
Sortie
4
Note
Il y a six zones, contenant respectivement $3, 1, 6, 2, 3, 1$ coquillages. Le OU exclusif bit à bit est égal à $3 \oplus 1 \oplus 6 \oplus 2 \oplus 3 \oplus 1 = 4$.
