兩個朋友在沙灘上收集了 $n^2$ 個貝殼，並將它們排成一個 $n$ 列 $n$ 行的網格。接著，他們在沙地上畫了一些水平線和垂直線，將沙灘劃分為若干個區域，每個區域內都含有正數個貝殼。

現在，朋友們在玩一個著名的 Nim 遊戲。他們輪流操作；在每次操作中，玩家可以從任意一個單一區域中拿走正數個貝殼。拿走最後一個貝殼的玩家獲勝。

朋友們知道，為了確定先手是否有必勝策略以及哪一步是最佳移動，應該計算每個區域中的貝殼數量，並計算這些數量的位元互斥或（bitwise 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$。