Naman 有两个长度为 $$$n$$$ 的二进制字符串 $$$s$$$ 和 $$$t$$$(二进制字符串是仅由字符“0”和“1”组成的字符串)。他希望尽可能少地使用以下操作将 $$$s$$$ 转换为 $$$t$$$。
在一次操作中,他可以选择 $$$s$$$ 的任意子序列并将其顺时针旋转一次。
例如,如果$$$s = 1\textbf{1}101\textbf{00}$$$,他可以选择索引(基于$$$1$$$的)$$$\{2, 6, 7 \}$$$对应的子序列并顺时针旋转它们。结果字符串将为 $$$s = 1\textbf{0}101\textbf{10}$$$。
如果通过删除一些字符而不改变剩余字符的顺序可以从 $$$b$$$ 获得 $$$a$$$,则字符串 $$$a$$$ 被称为字符串 $$$b$$$ 的子序列。
对大小为 $$$k$$$ 的序列 $$$c$$$ 执行顺时针旋转,就是执行同时设置 $$$c_1:=c_k, c_2:=c_1, c_3:=c_2, \ldots, c_k:=c_{k-1}$$$ 的操作。
确定 Naman 将 $$$s$$$ 转换为 $$$t$$$ 所需执行的最少操作数,或者说这是不可能的。
输入
第一行包含一个整数 $$$n$$$ $$$(1 \le n \le 10^6)$$$ — 字符串的长度。
第二行包含长度为 $$$n$$$ 的二进制字符串 $$$s$$$。
第三行包含长度为$$$n$$$的二进制字符串$$$t$$$。
输出
如果在任意次数的操作之后都无法将 $$$s$$$ 转换为 $$$t$$$,则打印 $$$-1$$$。
否则,打印所需的最少操作数。
示例
输入 #1
6 010000 000001
输出 #1
1
输入 #2
10 1111100000 0000011111
输出 #2
5
输入 #3
8 10101010 01010101
输出 #3
1
输入#4
10 1111100000 1111100001
输出#4
-1
注意
在第一个测试中,Naman 可以选择索引 $$$\{2, 6\}$$$ 对应的子序列并旋转一次,将 $$$s$$$ 转换为 $$$t$$$。
在第二个测试中,他可以将所有索引对应的子序列旋转$$$5$$$次。可以证明,这是所需的最少运算次数。
在上次测试中,无法将 $$$s$$$ 转换为 $$$t$$$。