Dwóch przyjaciół zebrało na plaży $n^2$ muszelek i ułożyło je w siatkę składającą się z $n$ wierszy i $n$ kolumn. Następnie narysowali na piasku pewną liczbę linii poziomych i pionowych, co podzieliło plażę na strefy, z dodatnią liczbą muszelek z ich kolekcji w każdej strefie.

Teraz przyjaciele grają w dobrze znaną grę Nim. Wykonują ruchy na przemian; w każdym ruchu gracz zabiera dodatnią liczbę muszelek z dowolnej jednej strefy. Wygrywa gracz, który zabierze ostatnie muszelki.

Przyjaciele wiedzą, że aby ustalić, czy pierwszy gracz ma strategię wygrywającą i który ruch jest optymalny, należy policzyć muszelki w każdej strefie i obliczyć bitowy XOR tych liczb. Brzmi to jak mnóstwo pracy. Pomóż im!

Wejście

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą $n$ ($1 \le n \le 10^6$). Zakładamy, że wiersze są ponumerowane od $1$ do $n$, z góry na dół. Kolumny również są ponumerowane od $1$ do $n$, od lewej do prawej.

Drugi wiersz zawiera napis złożony z $n - 1$ cyfr 0 lub 1; $i$-ta cyfra ($1 \le i < n$) jest równa 1, jeśli między wierszem $i$ a wierszem $i + 1$ znajduje się linia pozioma.

Trzeci wiersz zawiera napis złożony z $n - 1$ cyfr 0 lub 1; $i$-ta cyfra ($1 \le i < n$) jest równa 1, jeśli między kolumną $i$ a kolumną $i + 1$ znajduje się linia pionowa.

Wyjście

Wypisz jedną liczbę całkowitą — bitowy XOR liczb muszelek we wszystkich strefach.

Przykład

Wejście

4
001
101

Wyjście

4

Uwaga

Istnieje sześć stref mających odpowiednio $3, 1, 6, 2, 3, 1$ muszelek. Bitowy XOR jest równy $3 \oplus 1 \oplus 6 \oplus 2 \oplus 3 \oplus 1 = 4$.