A10095 | Hamming Distance Sum

Genos needs your help. He was asked to solve the following programming problem by Saitama:

The length of some string $s$ is denoted $|s|$ . The Hamming distance between two strings $s$ and $t$ of equal length is defined as , where $s_{i}$ is the $i$ -th character of $s$ and $t_{i}$ is the $i$ -th character of $t$ . For example, the Hamming distance between string "0011" and string "0110" is $|0-0|+|0-1|+|1-1|+|1-0|=0+1+0+1=2$ .

Given two binary strings $a$ and $b$ , find the sum of the Hamming distances between $a$ and all contiguous substrings of $b$ of length $|a|$ .

The first line of the input contains binary string $a$ ( $1<=|a|<=200000$ ).

The second line of the input contains binary string $b$ ( $|a|<=|b|<=200000$ ).

Both strings are guaranteed to consist of characters '0' and '1' only.

Print a single integer — the sum of Hamming distances between $a$ and all contiguous substrings of $b$ of length $|a|$ .