两个朋友在沙滩上收集了 $n^2$ 个贝壳，并将它们排成一个 $n$ 行 $n$ 列的网格。然后，他们在沙地上画了一些水平线和垂直线，将沙滩划分为若干个区域，每个区域内都含有正数个贝壳。

现在，朋友们在玩一个著名的 Nim 游戏。他们轮流操作；每次操作中，玩家可以从任意一个区域中拿走正数个贝壳。拿走最后一个贝壳的玩家获胜。

朋友们知道，为了确定先手是否有必胜策略以及哪一步是最佳移动，应该计算每个区域中的贝壳数量，并计算这些数量的按位异或和。这听起来工作量很大。帮帮他们！

输入格式

输入的第一行包含一个整数 $n$（$1 \le n \le 10^6$）。我们假设行从上到下编号为 $1$ 到 $n$。列也从左到右编号为 $1$ 到 $n$。

第二行包含一个由 $n - 1$ 个数字 0 或 1 组成的字符串；如果第 $i$ 行和第 $i + 1$ 行之间有一条水平线，则第 $i$ 个数字（$1 \le i < n$）为 1。

第三行包含一个由 $n - 1$ 个数字 0 或 1 组成的字符串；如果第 $i$ 列和第 $i + 1$ 列之间有一条垂直线，则第 $i$ 个数字（$1 \le i < n$）为 1。

输出格式

输出一个整数，即所有区域中贝壳数量的按位异或和。

样例

输入样例 1

4
001
101

输出样例 1

4

说明

共有六个区域，分别含有 3, 1, 6, 2, 3, 1 个贝壳。按位异或和等于 $3 \oplus 1 \oplus 6 \oplus 2 \oplus 3 \oplus 1 = 4$。