1186C · Vus the Cossack and Strings

Problem: 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.

Input Format: 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 Format: Print one number — the answer.

Note: The first example is explained in the legend.

In the second example, there are five substrings that satisfy us: $1010$, $0101$, $1111$, $1111$.