Два друга собрали на пляже $n^2$ ракушек и разложили их в виде таблицы из $n$ строк и $n$ столбцов. Затем они начертили на песке несколько горизонтальных и вертикальных линий, которые разделили пляж на зоны, так что в каждой зоне оказалось положительное число ракушек из их коллекции.
Теперь друзья играют в хорошо известную игру Ним. Они ходят по очереди; за один ход игрок берёт положительное количество ракушек из любой одной зоны. Выигрывает тот, кто заберёт последние ракушки.
Друзья знают, что для того чтобы определить, есть ли у первого игрока выигрышная стратегия и какой ход является оптимальным, нужно посчитать количество ракушек в каждой зоне и вычислить побитовое исключающее ИЛИ (XOR) этих чисел. Звучит как очень много работы. Помогите им!
Входные данные
Первая строка входных данных содержит одно целое число $n$ ($1 \le n \le 10^6$). Будем считать, что строки пронумерованы от $1$ до $n$ сверху вниз, а столбцы — от $1$ до $n$ слева направо.
Вторая строка содержит строку из $n - 1$ цифр 0 или 1; $i$-я цифра ($1 \le i < n$) равна 1, если между строкой $i$ и строкой $i + 1$ проведена горизонтальная линия.
Третья строка содержит строку из $n - 1$ цифр 0 или 1; $i$-я цифра ($1 \le i < n$) равна 1, если между столбцом $i$ и столбцом $i + 1$ проведена вертикальная линия.
Выходные данные
Выведите одно целое число — побитовое исключающее ИЛИ количества ракушек во всех зонах.
Пример
Входные данные
4 001 101
Выходные данные
4
Примечание
Всего шесть зон, содержащих $3, 1, 6, 2, 3, 1$ ракушек соответственно. Побитовое исключающее ИЛИ равно $3 \oplus 1 \oplus 6 \oplus 2 \oplus 3 \oplus 1 = 4$.
