2 人の友人が砂浜で $n^2$ 個の貝殻を集め、それらを $n$ 行 $n$ 列のグリッド状に並べました。その後、彼らは砂の上にいくつかの水平線といくつかの垂直線を引き、砂浜をいくつかの区画に分割しました。各区画には集めた貝殻が正の個数ずつ含まれています。

いま、友人たちはよく知られたニム（Nim）のゲームをして遊びます。彼らは交互に手番を行い、各手番ではプレイヤーがどれか 1 つの区画から正の個数の貝殻を取り除きます。最後の貝殻を取ったプレイヤーの勝ちです。

先手に必勝戦略があるかどうか、そしてどの手が最適であるかを判定するには、すべての区画にある貝殻の個数を数え、それらのビットごとの排他的論理和（XOR）を計算すればよいことを彼らは知っています。しかし、それはとても大変そうです。彼らを助けてあげましょう！

入力

入力の 1 行目には 1 つの整数 $n$（$1 \le n \le 10^6$）が与えられます。行には上から下へ $1$ から $n$ までの番号が付けられており、列にも左から右へ $1$ から $n$ までの番号が付けられているものとします。

2 行目には 0 または 1 からなる長さ $n - 1$ の文字列が与えられます。$i$ 番目の文字（$1 \le i < n$）は、第 $i$ 行と第 $i + 1$ 行の間に水平線があるとき 1 です。

3 行目には 0 または 1 からなる長さ $n - 1$ の文字列が与えられます。$i$ 番目の文字（$1 \le i < n$）は、第 $i$ 列と第 $i + 1$ 列の間に垂直線があるとき 1 です。

出力

すべての区画における貝殻の個数のビットごとの排他的論理和（XOR）を表す単一の整数を出力してください。

入出力例

入力例 1

4
001
101

出力例 1

4

注記

6 つの区画があり、それぞれに $3, 1, 6, 2, 3, 1$ 個の貝殻があります。ビットごとの排他的論理和は $3 \oplus 1 \oplus 6 \oplus 2 \oplus 3 \oplus 1 = 4$ に等しくなります。