Vus the Cossack 有两个二进制字符串,即仅由“0”和“1”组成的字符串。我们将这些字符串称为 $$$a$$$ 和 $$$b$$$。已知 $$$|b| \leq |a|$$$,即$$$b$$$的长度至多是$$$a$$$的长度。
哥萨克考虑字符串 $$$a$$$ 中长度为 $$$|b|$$$ 的每个子串。我们称这个子字符串为$$$c$$$。他匹配 $$$b$$$ 和 $$$c$$$ 中的相应字符,然后计算两个字符串不同的位置数。我们称这个函数为$$$f(b, c)$$$。
例如,让 $$$b = 00110$$$,$$$c = 11000$$$。在这些字符串中,第一、第二、第三和第四位置是不同的。
哥萨克人 Vus 计算这样的子串 $$$c$$$ 的数量,使得 $$$f(b, c)$$$ 是偶数。
例如,令 $$$a = 01100010$$$ 且 $$$b = 00110$$$。 $$$a$$$ 有四个长度为 $$$|b|$$$ 的子字符串:$$$01100$$$、$$$11000$$$、$$$10001$$$、$$$00010$$$。
- $$$f(00110, 01100) = 2$$$;
- $$$f(00110, 11000) = 4$$$;
- $$$f(00110, 10001) = 4$$$;
- $$$f(00110, 00010) = 1$$$。
由于三个子串中 $$$f(b, c)$$$ 是偶数,所以答案是 $$$3$$$。
Vus 找不到大字符串的答案。这就是为什么他要求你帮助他。
输入
第一行包含一个二进制字符串 $$$a$$$ ($$$1 \leq |a| \leq 10^6$$$) — 第一个字符串。
第二行包含一个二进制字符串 $$$b$$$ ($$$1 \leq |b| \leq |a|$$$) — 第二个字符串。
输出
打印一个数字——答案。
示例
输入 #1
01100010 00110
输出 #1
3
输入 #2
1010111110 0110
输出 #2
4
注意
第一个示例在图例中进行了解释。
在第二个例子中,有五个子字符串满足我们的要求:$$$1010$$$、$$$0101$$$、$$$1111$$$、$$$1111$$$。