Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

C. Vus the Cossack and Strings

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputVus 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

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.

Examples

Input

01100010 00110

Output

3

Input

1010111110 0110

Output

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$$$.

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/18/2019 20:41:35 (e1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|