Vus the Cossack and Strings
Description
Vus the Cossack has two binary strings, that is, strings that consist only of "0" and "1". We call these strings $a$ and $b$. It is known that $|b| \leq |a|$, that is, the length of $b$ is at most the length of $a$.
The Cossack considers every substring of length $|b|$ in string $a$. Let's call this substring $c$. He matches the corresponding characters in $b$ and $c$, after which he counts the number of positions where the two strings are different. We call this function $f(b, c)$.
For example, let $b = 00110$, and $c = 11000$. In these strings, the first, second, third and fourth positions are different.
Vus the Cossack counts the number of such substrings $c$ such that $f(b, c)$ is even.
For example, let $a = 01100010$ and $b = 00110$. $a$ has four substrings of the length $|b|$: $01100$, $11000$, $10001$, $00010$.
- $f(00110, 01100) = 2$;
- $f(00110, 11000) = 4$;
- $f(00110, 10001) = 4$;
- $f(00110, 00010) = 1$.
Since in three substrings, $f(b, c)$ is even, the answer is $3$.
Vus can not find the answer for big strings. That is why he is asking you to help him.
The first line contains a binary string $a$ ($1 \leq |a| \leq 10^6$) — the first string.
The second line contains a binary string $b$ ($1 \leq |b| \leq |a|$) — the second string.
Print one number — the answer.
Input
The first line contains a binary string $a$ ($1 \leq |a| \leq 10^6$) — the first string.
The second line contains a binary string $b$ ($1 \leq |b| \leq |a|$) — the second string.
Output
Print one number — the answer.
Samples
01100010
00110
3
1010111110
0110
4
Note
The first example is explained in the legend.
In the second example, there are five substrings that satisfy us: $1010$, $0101$, $1111$, $1111$.