Two friends collected $n^2$ shells at a beach, and arranged them in a grid of $n$ rows and $n$ columns. They then drew some horizontal and some vertical lines in the sand, which partitioned the beach into zones, with a positive number of shells from their collection in each zone.

Now, the friends play a well-known game of Nim. They make alternating moves; in each move, a player takes a positive number of shells from any single zone. The player who takes the last shells wins.

The friends know that to determine whether the first player has a winning strategy, and which move is optimal, one should count the number of shells in every zone and calculate the bitwise xor of these numbers. That sounds like a lot of work. Help them!

Input

The first line of the input contains one integer $n$ ($1 \le n \le 10^6$). We assume that the rows are numbered $1$ through $n$, top to bottom. The columns are also numbered $1$ through $n$, left to right.

The second line contains a string of $n - 1$ digits 0 or 1; the $i$-th digit ($1 \le i < n$) is 1 if there is a horizontal line between row $i$ and row $i + 1$.

The third line contains a string of $n - 1$ digits 0 or 1; the $i$-th digit ($1 \le i < n$) is 1 if there is a vertical line between column $i$ and column $i + 1$.

Output

Output a single integer, the bitwise xor of the numbers of shells in all zones.

Example

Input

4
001
101

Output

4

Note

There are six zones, having $3, 1, 6, 2, 3, 1$ shells, respectively. The bitwise xor is equal to $3 \oplus 1 \oplus 6 \oplus 2 \oplus 3 \oplus 1 = 4$.