Due amici hanno raccolto $n^2$ conchiglie su una spiaggia e le hanno disposte in una griglia di $n$ righe e $n$ colonne. Hanno poi tracciato alcune linee orizzontali e alcune linee verticali nella sabbia, suddividendo la spiaggia in zone, ciascuna contenente un numero positivo di conchiglie della loro collezione.
Ora gli amici giocano al famoso gioco di Nim. Si alternano nelle mosse; in ogni mossa, un giocatore prende un numero positivo di conchiglie da una singola zona qualsiasi. Vince il giocatore che prende le ultime conchiglie.
Gli amici sanno che per determinare se il primo giocatore ha una strategia vincente e quale mossa sia ottimale, bisogna contare il numero di conchiglie in ogni zona e calcolare lo XOR bit a bit di questi numeri. Sembra un sacco di lavoro. Aiutali!
Input
La prima riga dell'input contiene un intero $n$ ($1 \le n \le 10^6$). Assumiamo che le righe siano numerate da $1$ a $n$, dall'alto verso il basso. Anche le colonne sono numerate da $1$ a $n$, da sinistra a destra.
La seconda riga contiene una stringa di $n - 1$ cifre 0 oppure 1; la $i$-esima cifra ($1 \le i < n$) è 1 se c'è una linea orizzontale tra la riga $i$ e la riga $i + 1$.
La terza riga contiene una stringa di $n - 1$ cifre 0 oppure 1; la $i$-esima cifra ($1 \le i < n$) è 1 se c'è una linea verticale tra la colonna $i$ e la colonna $i + 1$.
Output
Stampa un singolo intero, lo XOR bit a bit del numero di conchiglie in tutte le zone.
Esempio
Input
4 001 101
Output
4
Note
Ci sono sei zone, aventi rispettivamente $3, 1, 6, 2, 3, 1$ conchiglie. Lo XOR bit a bit è uguale a $3 \oplus 1 \oplus 6 \oplus 2 \oplus 3 \oplus 1 = 4$.
