兩個朋友喺沙灘上面執咗 $n^2$ 個貝殼，將佢哋排成一個 $n$ 行 $n$ 列嘅網格。跟住，佢哋喺沙地上面畫咗一啲水平線同垂直線，將個沙灘劃分成若干個區域，每個區域入面都有正數個貝殼。

而家，呢兩個朋友玩緊一個出名嘅 Nim 遊戲。佢哋輪流行動；每次行動入面，玩家可以由任意一個單一區域入面攞走正數個貝殼。攞走最後啲貝殼嘅玩家就贏。

佢哋知道，為咗判斷先手有冇必勝策略同埋邊一步係最佳行法，應該數出每個區域入面嘅貝殼數量，並計算呢啲數量嘅按位異或（bitwise xor）。聽落功夫唔少，快啲幫下佢哋啦！

輸入格式

輸入嘅第一行包含一個整數 $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。

輸出格式

輸出一個整數，代表所有區域入面貝殼數量嘅按位異或和。

範例

輸入

4
001
101

輸出

4

備註

總共有六個區域，分別有 $3, 1, 6, 2, 3, 1$ 個貝殼。按位異或和等於 $3 \oplus 1 \oplus 6 \oplus 2 \oplus 3 \oplus 1 = 4$。