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 $\sum_{i = 1}^{|s|}|s_{i} - t_{i}|$, 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|.


-----Input-----

The first line of the input contains binary string a (1 ≤ |a| ≤ 200 000).

The second line of the input contains binary string b (|a| ≤ |b| ≤ 200 000).

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


-----Output-----

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


-----Examples-----
Input
01
00111

Output
3

Input
0011
0110

Output
2



-----Note-----

For the first sample case, there are four contiguous substrings of b of length |a|: "00", "01", "11", and "11". The distance between "01" and "00" is |0 - 0| + |1 - 0| = 1. The distance between "01" and "01" is |0 - 0| + |1 - 1| = 0. The distance between "01" and "11" is |0 - 1| + |1 - 1| = 1. Last distance counts twice, as there are two occurrences of string "11". The sum of these edit distances is 1 + 0 + 1 + 1 = 3.

The second sample case is described in the statement.

Difficulty: MEDIUM
Tags: String algorithms

Combinatorics
Expected Time Complexity: O(N)

Starter code:

Solutions:
sub = input().rstrip()
s = input().rstrip()

def sumRange(left, right):
	return psums[right + 1] - psums[left]
n = len(s)
subSize = len(sub)
psums = [0]
for (i, ch) in enumerate(sub):
	psums.append(psums[-1] + int(ch))
ret = 0
for i in range(len(s)):
	ch = s[i]
	left = max(0, i + subSize - n)
	right = min(i, subSize - 1)
	oneCnt = sumRange(left, right)
	size = right - left + 1
	ret += oneCnt if ch == '0' else size - oneCnt
print(ret)


a = input()
b = input()
t = 0
ans = 0
p = len(b) - len(a) + 1
for i in range(len(b) - len(a) + 1):
	t += int(b[i])
for j in range(len(a)):
	v = int(a[j])
	if v == 1:
		ans = ans + p - t
	else:
		ans = ans + t
	if j == len(a) - 1:
		break
	t = t + int(b[p + j])
	t = t - int(b[j])
print(ans)


a = [int(i) for i in list(input())]
b = [int(i) for i in list(input())]
aa = len(a)
bb = len(b)
l = t = 0
t = bb - aa + 1
ans = 0
for i in range(bb - aa + 1):
	l += int(b[i])
for i in range(aa):
	if a[i] == 1:
		ans += t - l
	else:
		ans += l
	if i == len(a) - 1:
		break
	l += int(b[t + i])
	l -= int(b[i])
print(ans)


from sys import stdin
s = stdin.readline().strip()
s1 = stdin.readline().strip()
ones = [0 for i in range(len(s1) + 10)]
zeros = [0 for i in range(len(s1) + 10)]
for i in range(len(s1)):
	if s1[i] == '1':
		ones[i] = 1
	else:
		zeros[i] = 1
	if i > 0:
		ones[i] += ones[i - 1]
		zeros[i] += zeros[i - 1]
r = len(s1) - len(s)
ans = 0
for i in range(len(s)):
	if s[i] == '0':
		ans += ones[r] - ones[i - 1]
	else:
		ans += zeros[r] - zeros[i - 1]
	r += 1
print(ans)


__author__ = 'MoonBall'
import sys
T = 1

def process():
	a = input()
	b = input()
	zero = [0] * 210000
	for (i, c) in enumerate(a):
		zero[i + 1] = zero[i] + (1 if c == '0' else 0)
	ans = 0
	for (i, c) in enumerate(b):
		s = max(1, len(a) - (len(b) - i) + 1)
		e = min(i + 1, len(a))
		z = 1 if c == '0' else 0
		o = 1 - z
		ans += z * (e - s + 1 - (zero[e] - zero[s - 1]))
		ans += o * (zero[e] - zero[s - 1])
	print(ans)
for _ in range(T):
	process()


a = input()
b = input()
lb = len(b)
la = len(a)
(c0, c1) = (b[0:lb - la + 1].count('0'), b[0:lb - la + 1].count('1'))
s = c0 if a[0] == '1' else c1
for i in range(1, la):
	if int(b[i - 1]) == 1:
		c1 -= 1
	else:
		c0 -= 1
	if int(b[i + lb - la]) == 1:
		c1 += 1
	else:
		c0 += 1
	s += c1 if a[i] == '0' else c0
print(s)


def solve():
	S = input()
	T = input()
	lens = len(S)
	lent = len(T)
	a0 = [0] * lens
	a1 = [0] * lens
	for i in range(lens):
		if i > 0:
			a0[i] = a0[i - 1]
			a1[i] = a1[i - 1]
		if S[i] == '0':
			a1[i] += 1
		else:
			a0[i] += 1
	ans = 0
	for i in range(lens):
		if T[i] == '0':
			ans += a0[i]
		else:
			ans += a1[i]
	for i in range(lens, lent):
		if T[i] == '0':
			ans += a0[-1]
		else:
			ans += a1[-1]
	for i in range(lent - lens + 1, lent):
		d = lent - i
		if T[i] == '0':
			ans -= a0[-d - 1]
		else:
			ans -= a1[-d - 1]
	print(ans)
solve()


import sys
a = sys.stdin.readline().rstrip()
b = sys.stdin.readline().rstrip()
(la, lb) = (len(a), len(b))
(sum, cur) = (0, 0)
for i in range(lb - la + 1):
	cur += int(b[i])
for i in range(la):
	if a[i] == '0':
		sum += cur
	else:
		sum += lb - la + 1 - cur
	if i != la - 1:
		if b[i] == '1':
			cur -= 1
		if b[lb - la + i + 1] == '1':
			cur += 1
print(sum)


(a, b, c, d, e) = (input(), input(), [0], 0, 0)
for i in range(len(b)):
	d += int(b[i])
	c.append(d)
for i in range(len(a)):
	nOO = c[len(b) - (len(a) - i) + 1] - c[i]
	nOZ = len(b) - len(a) + 1 - nOO
	if a[i] == '0':
		e += nOO
	else:
		e += nOZ
print(e)


(a, b) = (input(), input())
c = [[0] * 210000, [0] * 210000]
for (i, d) in enumerate(b):
	for t in range(2):
		c[t][i + 1] = c[t][i] + (d == str(t))
print(sum((c[int(t) ^ 1][len(b) - len(a) + 1 + i] - c[int(t) ^ 1][i] for (i, t) in enumerate(a))))


a = input()
b = input()
l = len(a)
n = len(b)
ans = 0
(ans1, ans0) = ([0], [0])
(count0, count1) = (0, 0)
for i in range(n):
	if b[i] == '0':
		count0 += 1
		ans1.append(count1)
		ans0.append(count0)
	else:
		count1 += 1
		ans1.append(count1)
		ans0.append(count0)
for i in range(len(a)):
	if a[i] == '0':
		ans += abs(ans1[n - l + i + 1] - ans1[i])
	else:
		ans += abs(ans0[n - l + i + 1] - ans0[i])
print(ans)


a = list(map(int, list(input())))
b = list(map(int, list(input())))
v = list()
n = len(b) - len(a)
s = 0
for i in range(n + 1):
	s += b[i]
v.append(s)
for i in range(1, len(a)):
	v.append(v[i - 1] + b[n + i] - b[i - 1])
r = 0
for i in range(len(a)):
	if a[i] == 0:
		r += v[i]
	else:
		r += n + 1 - v[i]
print(r)


(a, b) = (input(), input())
ans = 0
ones = [0 for i in range(len(b) + 1)]
zeros = [0 for i in range(len(b) + 1)]
for i in range(len(b)):
	ones[i] = ones[i - 1] + int(b[i])
	zeros[i] = i + 1 - ones[i]
for i in range(len(a)):
	if a[i] == '1':
		ans += zeros[len(b) - len(a) + i] - zeros[i - 1]
	else:
		ans += ones[len(b) - len(a) + i] - ones[i - 1]
print(ans)


from sys import stdin, stdout
from math import gcd, sqrt, factorial, pi
from collections import deque, defaultdict
input = stdin.readline
R = lambda : map(int, input().split())
I = lambda : int(input())
S = lambda : input().rstrip('\n')
L = lambda : list(R())
P = lambda x: stdout.write(x)
lcm = lambda x, y: x * y // gcd(x, y)
hg = lambda x, y: (y + x - 1) // x * x
pw = lambda x: 1 if x == 1 else 1 + pw(x // 2)
chk = lambda x: chk(x // 2) if not x % 2 else True if x == 1 else False
sm = lambda x: (x ** 2 + x) // 2
N = 10 ** 9 + 7

def binary(l, r, a, k):
	v = a[l]
	ans = l
	while l <= r:
		m = (l + r) // 2
		if a[m] - v <= k:
			ans = max(ans, m)
			l = m + 1
		else:
			r = m - 1
	return ans
a = [int(i) for i in S()]
b = [int(i) for i in S()]
d = [[0, 0]]
p = [0, 0]
for i in b:
	p[i] += 1
	d.append(p.copy())
ans = 0
n = len(a)
m = len(d)
for i in range(n):
	ans += [d[m - (n - i)][0] - d[i][0], d[m - (n - i)][1] - d[i][1]][a[i] ^ 1]
print(ans)


s = [bool(int(i)) for i in input()]
n = [bool(int(i)) for i in input()]
k = 0
a = 0
b = 0
n1 = [0]
for i in n:
	a += i
	n1.append(a)
for i in range(len(s)):
	if not s[i]:
		k += n1[len(n) - len(s) + i + 1] - n1[i]
	else:
		k += len(n) - len(s) + i + 1 - n1[len(n) - len(s) + i + 1] - (i - n1[i])
print(k)


import sys
import string
import math
from collections import defaultdict
from functools import lru_cache
from collections import Counter
from fractions import Fraction

def mi(s):
	return map(int, s.strip().split())

def lmi(s):
	return list(mi(s))

def tmi(s):
	return tuple(mi(s))

def mf(f, s):
	return map(f, s)

def lmf(f, s):
	return list(mf(f, s))

def js(lst):
	return ' '.join((str(d) for d in lst))

def line():
	return sys.stdin.readline().strip()

def linesp():
	return line().split()

def iline():
	return int(line())

def mat(n):
	matr = []
	for _ in range(n):
		matr.append(linesp())
	return matr

def matns(n):
	mat = []
	for _ in range(n):
		mat.append([c for c in line()])
	return mat

def mati(n):
	mat = []
	for _ in range(n):
		mat.append(lmi(line()))
	return mat

def pmat(mat):
	for row in mat:
		print(js(row))

def dist(x, y):
	return ((x[0] - y[0]) ** 2 + (x[1] - y[1]) ** 2) ** 0.5

def fast_exp(x, n):
	if n == 0:
		return 1
	elif n % 2 == 1:
		return x * fast_exp(x, (n - 1) // 2) ** 2
	else:
		return fast_exp(x, n // 2) ** 2

def gcd(a, b):
	while b:
		a %= b
		(a, b) = (b, a)
	return a

def hamming_d(a, b, i, j):
	count = 0
	w = 0
	for k in range(i, j + 1):
		if a[w] != b[k]:
			count += 1
		w += 1
	return count

def main():
	s1 = line()
	s2 = line()
	prefix_b = [ord(s2[0]) - ord('0')]
	for i in range(1, len(s2)):
		prefix_b.append(prefix_b[-1] + ord(s2[i]) - ord('0'))
	count = 0
	for i in range(len(s1)):
		length = len(s2) - len(s1) + 1
		if i == 0:
			num_ones = prefix_b[len(s2) - len(s1) + i]
		else:
			num_ones = prefix_b[len(s2) - len(s1) + i] - prefix_b[i - 1]
		num_zeros = length - num_ones
		if s1[i] == '1':
			count += num_zeros
		else:
			count += num_ones
	print(count)
main()


import sys
a = input()
b = input()
l1 = len(a)
one = [0] * len(b)
zero = [0] * len(b)
cnt = cnt1 = cnt0 = 0
for i in range(len(b)):
	if b[i] == '1':
		cnt1 += 1
	elif b[i] == '0':
		cnt0 += 1
	one[i] = cnt1
	zero[i] = cnt0
last = len(b) - len(a)
first = -1
for i in range(l1):
	if a[i] == '0':
		if i == 0:
			cnt += one[last]
		else:
			cnt += one[last] - one[first]
	elif a[i] == '1':
		if i == 0:
			cnt += zero[last]
		else:
			cnt += zero[last] - zero[first]
	first += 1
	last += 1
print(cnt)


first = [int(i) for i in input()]
second = [int(i) for i in input()]
pref_dists = [[0] + [int(0 != c) for c in second], [0] + [int(1 != c) for c in second]]
for i in range(1, len(second) + 1):
	pref_dists[0][i] += pref_dists[0][i - 1]
	pref_dists[1][i] += pref_dists[1][i - 1]
total = 0
for (i, c) in enumerate(first):
	end = len(second) - (len(first) - i)
	total += pref_dists[c][end + 1] - pref_dists[c][i]
print(total)


(a, b) = (input(), input())
(alen, blen) = (len(a), len(b))
diff = blen - alen
count = b[:diff + 1].count('0')
result = 0
for i in range(0, alen):
	result += diff + 1 - count if a[i] == '0' else count
	if i == alen - 1:
		break
	count -= 1 if b[i] == '0' else 0
	count += 1 if b[diff + 1 + i] == '0' else 0
print(result)


s1 = input()
s2 = input()
zeros = 0
ones = 0
i = 0
j = -1
l1 = len(s1)
l2 = len(s2)
answ = 0
while j < l2 - l1:
	j += 1
	if s2[j] == '0':
		zeros += 1
	else:
		ones += 1
while j < l2:
	if s1[i] == '0':
		answ += ones
	else:
		answ += zeros
	if j == l2 - 1:
		break
	j += 1
	i += 1
	if s2[i - 1] == '0' and s2[j] == '1':
		zeros -= 1
		ones += 1
	elif s2[i - 1] == '1' and s2[j] == '0':
		zeros += 1
		ones -= 1
print(answ)


a = list(input())
a = [int(x) for x in a]
b = list(input())
b = [int(x) for x in b]
n = len(a)
m = len(b)
ans = 0
for i in range(n):
	ans += a[i] ^ b[i]
ones = [0 for i in range(m)]
zeros = [0 for i in range(m)]
for i in range(m):
	if b[i]:
		ones[i] = 1
	else:
		zeros[i] = 1
for i in range(1, m):
	ones[i] += ones[i - 1]
	zeros[i] += zeros[i - 1]
for i in range(n):
	if a[i] == 1:
		ans += zeros[m - n + i] - zeros[i]
	else:
		ans += ones[m - n + i] - ones[i]
print(ans)


a = input()
b = input()
o = []
z = []
c0 = 0
c1 = 0
for i in b:
	if i == '0':
		c0 += 1
	else:
		c1 += 1
	o.append(c1)
	z.append(c0)
n = len(b) - 1
m = len(a) - 1
ans = 0
for i in range(len(a)):
	x = a[i]
	if x == '1':
		ans += z[n - (m - i)] - z[i]
		if b[i] == '0':
			ans += 1
	else:
		ans += o[n - (m - i)] - o[i]
		if b[i] == '1':
			ans += 1
print(ans)


read = lambda : list(map(int, input()))
(a, b) = (read(), read())
(n, m) = (len(a), len(b))
cnt1 = [0] * (n + 1)
cnt0 = [0] * (n + 1)
if a[0]:
	cnt1[0] = 1
else:
	cnt0[0] = 1
for i in range(1, n):
	cnt1[i] = cnt1[i - 1]
	cnt0[i] = cnt0[i - 1]
	if a[i]:
		cnt1[i] += 1
	else:
		cnt0[i] += 1
Sum = 0
for i in range(m):
	L = max(0, n + i - m)
	R = min(n - 1, i)
	if b[i]:
		cur = cnt0[R] - cnt0[L - 1]
	else:
		cur = cnt1[R] - cnt1[L - 1]
	Sum += cur
print(Sum)


a = str(input())
b = str(input())
(n, m) = (len(a), len(b))
(ones, sum) = (0, 0)
diff = m - n + 1
for i in range(diff):
	if b[i] == '1':
		ones += 1
for i in range(n):
	if a[i] == '0':
		sum += ones
	else:
		sum += diff - ones
	if i == n - 1:
		break
	if b[i] == '1':
		ones -= 1
	if b[i + diff] == '1':
		ones += 1
print(sum)


a = input()
b = input()
lb = len(b)
la = len(a)
c = [[b[0:lb - la + 1].count('0'), b[0:lb - la + 1].count('1')]]
s = 0
if la == lb:
	for i in range(la):
		if a[i] != b[i]:
			s += 1
	print(s)
else:
	for i in range(1, la):
		c.append(c[i - 1][:])
		c[i][int(b[i - 1])] -= 1
		c[i][int(b[i + lb - la])] += 1
	for i in range(la):
		if a[i] == '0':
			s += c[i][1]
		else:
			s += c[i][0]
	print(s)


a = input()
b = input()
n = len(b)
m = len(a)
ans = 0
ones = [0] * (n + 1)
for i in range(1, n + 1):
	ones[i] = ones[i - 1] + int(b[i - 1])
for i in range(m):
	x = i
	y = n - m + i
	if a[i] == '0':
		ans += ones[y + 1] - ones[x]
	elif a[i] == '1':
		ans += abs(y - x + 1 - (ones[y + 1] - ones[x]))
print(ans)


(a, b, cum, total, ans) = (input(), input(), [0], 0, 0)
for i in range(len(b)):
	total += int(b[i])
	cum.append(total)
for i in range(len(a)):
	one = cum[len(b) - (len(a) - i) + 1] - cum[i]
	zero = len(b) - len(a) + 1 - one
	if a[i] == '0':
		ans += one
	else:
		ans += zero
print(ans)


a = input()
b = input()
range_count = len(b) - len(a) + 1
count_0 = b[:range_count].count('0')
result = count_0 if a[0] == '1' else range_count - count_0
for i in range(1, len(a)):
	if b[i - 1] != b[range_count + i - 1]:
		count_0 += 1 if b[i - 1] == '1' else -1
	result += count_0 if a[i] == '1' else range_count - count_0
print(result)


(a, b) = ('0' + input(), '0' + input())
(m, n) = (len(a), len(b))
(c, s) = ([0] * (n + 1), 0)
if m <= n:
	for i in range(1, n):
		c[i] = int(b[i]) + c[i - 1]
	for i in range(1, m):
		if a[i] == '0':
			s += c[i + n - m] - c[i - 1]
		else:
			s += n - m + 1 - (c[i + n - m] - c[i - 1])
print(s)


s = input()
t = input()
d = len(t) - len(s) + 1
ans = 0
l1 = [0]
for i in range(len(t)):
	if t[i] == '1':
		ans += 1
	l1.append(ans)
ans = 0
for i in range(len(s)):
	if s[i] == '0':
		ans += l1[d + i] - l1[i]
	else:
		ans += d - l1[d + i] + l1[i]
print(ans)


str1 = input()
str2 = input()
diff = len(str2) - len(str1)
arr1 = [0 for x in range(len(str2))]
arr2 = [0 for x in range(len(str2))]
if int(str2[0]) == 1:
	arr1[0] = 1
else:
	arr2[0] = 1
for x in range(1, len(str2)):
	if int(str2[x]) == 1:
		arr1[x] += arr1[x - 1] + 1
		arr2[x] = arr2[x - 1]
	else:
		arr2[x] += arr2[x - 1] + 1
		arr1[x] = arr1[x - 1]
ans = 0
if int(str1[0]) == 1:
	ans = arr2[diff]
else:
	ans = arr1[diff]
for x in range(1, len(str1)):
	if int(str1[x]) == 1:
		ans += arr2[x + diff] - arr2[x - 1]
	else:
		ans += arr1[x + diff] - arr1[x - 1]
print(ans)


a = input()
b = input()
l1 = len(a)
l2 = len(b)
pre_sum = [0] * l2
pre_sum[0] = b[0].count('1')
for i in range(1, l2):
	if b[i] == '1':
		pre_sum[i] = pre_sum[i - 1] + 1
	else:
		pre_sum[i] = pre_sum[i - 1]
ans = 0
if a[0] == '0':
	ans += pre_sum[l2 - l1]
else:
	ans += l2 - l1 + 1 - pre_sum[l2 - l1]
for i in range(1, l1):
	x = pre_sum[l2 - l1 + i] - pre_sum[i - 1]
	if a[i] == '0':
		ans += x
	else:
		ans += l2 - l1 + 1 - x
print(ans)


a = list(input())
b = list(input())
la = len(a)
lb = len(b)
s = 0
r = [0] * (lb + 1)
for i in range(1, lb + 1):
	r[i] = r[i - 1] + int(b[i - 1])
j = 0
for i in range(la - 1, -1, -1):
	t = r[lb - j] - r[i]
	k = lb - j - i
	if a[i] != '1':
		s += t
	else:
		s += k - t
	j += 1
print(s)


a = input()
b = input()
one_count = []
c = 0
for ch in b:
	one_count.append(c)
	if ch == '1':
		c += 1
one_count.append(c)
hamming = 0
len_a = len(a)
len_b = len(b)
for i in range(len_a):
	j = len_b - (len_a - i - 1)
	n_ones = one_count[j] - one_count[i]
	n_zeroes = j - i - n_ones
	hamming += n_ones if a[i] == '0' else n_zeroes
print(hamming)


a = input()
b = input()
cs = [0]
for ch in b:
	cs.append(cs[-1] + (ch == '1'))
diff = len(b) - len(a)
ans = 0
for (idx, ch) in enumerate(a):
	ones = cs[idx + diff + 1] - cs[idx - 1 + 1]
	zeros = diff + 1 - ones
	if ch == '1':
		ans += zeros
	else:
		ans += ones
print(ans)


a = input()
b = input()
zeros = [0]
ones = [0]
for (i, c) in enumerate(b):
	if c == '0':
		zeros.append(zeros[-1] + 1)
		ones.append(ones[-1])
	else:
		ones.append(ones[-1] + 1)
		zeros.append(zeros[-1])
res = 0
for (i, c) in enumerate(a):
	(inf, sup) = (i, len(b) - len(a) + i + 1)
	res += ones[sup] - ones[inf] if c == '0' else zeros[sup] - zeros[inf]
print(res)


a = input()
b = input()
l1 = len(a)
l2 = len(b)
a = 'X' + a
b = 'X' + b
ones = [0 for i in range(l2 + 1)]
zeros = [0 for i in range(l2 + 1)]
for i in range(1, l2 + 1):
	if b[i] == '0':
		zeros[i] = 1 + zeros[i - 1]
		ones[i] = ones[i - 1]
	else:
		zeros[i] = zeros[i - 1]
		ones[i] = 1 + ones[i - 1]
final = 0
for i in range(1, l1 + 1):
	if a[i] == '0':
		final += ones[l2 - l1 + i] - ones[i - 1]
	else:
		final += zeros[l2 - l1 + i] - zeros[i - 1]
print(final)


a = input()
b = input()
a1 = [0]
curr = 0
for i in b:
	if i == '1':
		curr += 1
	a1.append(curr)
a2 = [0]
curr = 0
for i in b:
	if i == '0':
		curr += 1
	a2.append(curr)
ans = 0
for i in range(len(a)):
	if a[i] == '0':
		t = a1[len(b) - len(a) + i + 1] - a1[i]
		if t >= 0:
			ans += t
		else:
			break
for i in range(len(a)):
	if a[i] == '1':
		t = a2[len(b) - len(a) + i + 1] - a2[i]
		if t >= 0:
			ans += t
		else:
			break
print(ans)


a = input()
b = input()
l = len(b)
p0 = [0] * (l + 1)
s0 = [0] * (l + 1)
p1 = [0] * (l + 1)
s1 = [0] * (l + 1)
for i in range(l):
	if b[i] == '0':
		p1[i + 1] = p1[i] + 1
		p0[i + 1] = p0[i]
	else:
		p0[i + 1] = p0[i] + 1
		p1[i + 1] = p1[i]
for i in range(l - 1, -1, -1):
	if b[i] == '0':
		s1[i] = s1[i + 1] + 1
		s0[i] = s0[i + 1]
	else:
		s0[i] = s0[i + 1] + 1
		s1[i] = s1[i + 1]
l1 = len(a)
res = 0
for i in range(l1):
	if a[i] == '0':
		res += p0[l] - p0[i] - s0[l - l1 + i + 1]
	if a[i] == '1':
		res += p1[l] - p1[i] - s1[l - l1 + i + 1]
print(res)


import sys
import math
import collections as cl
from pprint import pprint as pp
mod = 1000000007

def vector(size, val=0):
	vec = [val for i in range(size)]
	return vec

def matrix(rowNum, colNum, val=0):
	mat = []
	for i in range(rowNum):
		collumn = [val for j in range(colNum)]
		mat.append(collumn)
	return mat
(s, t) = (input(), input())
(n, m) = (len(s), len(t))
(x, y) = (vector(n), vector(n))
(c0, c1) = (0, 0)
for i in range(m - n + 1):
	if t[i] == '0':
		c0 += 1
	else:
		c1 += 1
(x[0], y[0]) = (c0, c1)
for i in range(1, n):
	if t[i + m - n] == '0':
		c0 += 1
	else:
		c1 += 1
	if t[i - 1] == '0':
		c0 -= 1
	else:
		c1 -= 1
	(x[i], y[i]) = (c0, c1)
ans = 0
for i in range(n):
	if s[i] == '0':
		ans += y[i]
	else:
		ans += x[i]
print(ans)


a = input()
b = input()
cs_one = [0]
for ai in a:
	cs_one.append(cs_one[-1] + int(ai == '1'))

def find_zeros_ones_in_range(l, r):
	n_ones = cs_one[r + 1] - cs_one[l]
	n_zeros = r - l + 1 - n_ones
	return (n_zeros, n_ones)
sum_hamming_dis = 0
for (i, bi) in enumerate(b):
	n_before = i
	n_after = len(b) - n_before - 1
	l = max(len(a) - 1 - n_after, 0)
	r = min(n_before, len(a) - 1)
	(nz, no) = find_zeros_ones_in_range(l, r)
	if bi == '0':
		sum_hamming_dis += no
	else:
		sum_hamming_dis += nz
print(sum_hamming_dis)


(a, b, c) = (input(), input(), 0)
p = [[0] * (len(b) + 1), [0] * (len(b) + 1)]
for i in range(0, len(b)):
	p[0][i + 1] = p[0][i] + int(b[i] == '0')
	p[1][i + 1] = p[1][i] + int(b[i] != '0')
for i in range(len(a)):
	cr = int(a[i] == '1')
	for j in range(2):
		c += abs(cr - j) * (p[j][len(b) - len(a) + i + 1] - p[j][i])
print(c)


a = list(input())
b = list(input())
m = len(a)
n = len(b)
ans = 0
pre = [0] * (n + 1)
for i in range(1, n + 1):
	pre[i] = pre[i - 1] + int(b[i - 1])
k = 0
for i in range(m - 1, -1, -1):
	sm = pre[n - k] - pre[i]
	length = n - k - i
	if a[i] == '0':
		ans += sm
	else:
		ans += length - sm
	k += 1
print(ans)


a = list(map(int, input()))
b = list(map(int, input()))
ps = [0] * (len(b) + 1)
for i in range(len(b)):
	ps[i + 1] = ps[i] + b[i]
ans = 0
for i in range(len(a)):
	left = i
	right = len(b) - len(a) + i + 1
	sub = ps[right] - ps[left]
	if a[i] == 1:
		sub = right - left - sub
	ans += sub
print(ans)


a = input()
b = input()
zero = [0]
ones = [0]
for i in range(len(b)):
	if b[i] == '0':
		zero.append(zero[-1] + 1)
		ones.append(ones[-1])
	else:
		ones.append(ones[-1] + 1)
		zero.append(zero[-1])
ans = 0
for i in range(len(a)):
	if a[i] == '0':
		ans += ones[len(b) - len(a) + i + 1] - ones[i]
	else:
		ans += zero[len(b) - len(a) + (i + 1)] - zero[i]
print(ans)


a = list(input())
b = list(input())
sum = 0
for i in range(len(a)):
	sum += int(a[i])
	a[i] = sum
a.insert(0, 0)
sum = 0
for i in range(len(b)):
	l = max(0, len(a) - 1 - (len(b) - i))
	r = min(len(a) - 2, i)
	col1 = a[r + 1] - a[l]
	col2 = r - l + 1 - col1
	if b[i] == '0':
		sum += col1
	else:
		sum += col2
print(sum)


a = input()
b = input()
al = len(a)
bl = len(b)
num = bl - al + 1
num2 = 0
for i in range(num):
	if a[0] != b[i]:
		num2 += 1
num3 = num2
for i in range(1, al):
	if a[i - 1] != a[i]:
		if a[i] == b[i - 1]:
			num2 -= 1
		num2 = num - num2 - 1
	elif a[i] != b[i - 1]:
		num2 -= 1
	if a[i] != b[i + num - 1]:
		num2 += 1
	num3 += num2
print(num3)


a = str(input())
b = str(input())
n = len(a)
m = len(b)
ans = 0
c = m - n + 1
ones = 0
for i in range(c):
	if b[i] == '1':
		ones += 1
for i in range(n):
	if a[i] == '0':
		ans += ones
	else:
		ans += c - ones
	if i == n - 1:
		break
	if b[i] == '1':
		ones -= 1
	if b[i + c] == '1':
		ones += 1
print(ans)


cache = {}

def countOnes(number):
	counter = 0
	while number != 0:
		counter += 1
		number = number & number - 1
	return counter

def populateCache(string, aLen):
	ones = 0
	zeroes = 0
	index = len(string) - aLen + 1
	for i in range(len(string) - 1, -1, -1):
		if string[i] == '1':
			ones += 1
		else:
			zeroes += 1
		cache[i] = (ones, zeroes)
	for i in range(0, aLen - 1, 1):
		(ones, zeroes) = cache[i]
		cache[i] = (ones - cache[index][0], zeroes - cache[index][1])
		index += 1

def matchingStrings(a, b):
	return countOnes(int(a, 2) ^ int(b, 2))
total = 0
a = str(input())
aLen = len(a)
b = str(input())
bLen = len(b)
if aLen == bLen:
	print(matchingStrings(a, b))
else:
	populateCache(b, aLen)
	for (index, ele) in enumerate(a):
		num = int(ele)
		if num == 0:
			total += cache[index][0]
		else:
			total += cache[index][1]
	print(total)


a = input()
b = input()
step = len(b) - len(a) + 1
zeroes = b[:step].count('0')
result = zeroes if a[0] == '1' else step - zeroes
for i in range(1, len(a)):
	if b[i - 1] != b[step + i - 1]:
		zeroes += 1 if b[i - 1] == '1' else -1
	result += zeroes if a[i] == '1' else step - zeroes
print(result)


a = input()
b = input()
al = [int(ai) for ai in a]
bl = [int(bi) for bi in b]

def f(al, bl):
	s = 0
	e = len(bl) - len(al) + 1
	c0 = 0
	c1 = 0
	sum = 0
	for i in range(s, e):
		if bl[i] == 1:
			c1 += 1
		else:
			c0 += 1
	for i in range(s, len(al)):
		curr = al[i]
		sum += curr * c0 + (not curr) * c1
		if bl[s] == 1:
			c1 -= 1
		else:
			c0 -= 1
		if e < len(bl):
			if bl[e] == 1:
				c1 += 1
			else:
				c0 += 1
		s += 1
		e += 1
	return sum
print(f(al, bl))


a = list(input())
b = list(input())
n = len(a)
bn = len(b)
MAXN = int(200000.0 + 10)
pre0 = [0] * MAXN
pre1 = [0] * MAXN
if b[0] == '1':
	pre1[0] = 1
else:
	pre0[0] = 1
for i in range(1, bn):
	pre0[i] = pre0[i - 1]
	pre1[i] = pre1[i - 1]
	if b[i] == '0':
		pre0[i] += 1
	else:
		pre1[i] += 1
ans = 0
k = bn - n
if a[0] == '1':
	ans += pre0[k]
else:
	ans += pre1[k]
for i in range(1, n):
	if a[i] == '1':
		ans += pre0[k + i] - pre0[i - 1]
	else:
		ans += pre1[k + i] - pre1[i - 1]
print(ans)


a = input()
b = input()
ans = 0
p = [0 for i in range(len(b) + 1)]
for i in range(len(b)):
	p[i + 1] = p[i] + int(b[i])
for i in range(len(a)):
	ans += abs(int(a[i]) * (len(b) - len(a) + 1) - p[len(b) - len(a) + i + 1] + p[i])
print(ans)


from sys import stdin
input = stdin.readline

def getcnt(a):
	cnt = [[0, 0] for i in range(len(a))]
	for i in range(len(a)):
		if i == 0:
			cnt[i][a[i]] += 1
		else:
			cnt[i][0] = cnt[i - 1][0]
			cnt[i][1] = cnt[i - 1][1]
			cnt[i][a[i]] += 1
	return cnt

def f(a, b):
	ans = 0
	a = list(map(int, list(a)))
	b = list(map(int, list(b)))
	lb = len(b)
	la = len(a)
	cnt = getcnt(a)
	ans = 0
	for i in range(len(b)):
		lo = max(0, i - (lb - la))
		hi = min(i, la - 1)
		if lo == 0:
			lr = [0, 0]
		else:
			lr = cnt[lo - 1]
		rr = cnt[hi]
		t = list(map(lambda x, y: x - y, rr, lr))
		ans += t[b[i] ^ 1]
	return ans
s = input().strip()
t = input().strip()
print(f(s, t))


(a, b, s, res) = (' ' + input(), ' ' + input(), [0], 0)
(n, m) = (len(a) - 1, len(b) - 1)
for i in range(1, n + 1):
	s.append(s[i - 1] + (a[i] == '1'))
for i in range(1, m + 1):
	(l, r) = (1 if m - i + 1 >= n else n + i - m, min(n, i))
	if b[i] == '0':
		res += s[r] - s[l - 1]
	else:
		res += r - l + 1 - s[r] + s[l - 1]
print(res)


import math
a = input()
b = input()
shift = [0]
for i in range(len(b) - len(a) + 1):
	shift[0] += int(b[i])
for i in range(len(a) - 1):
	shift.append(shift[i] - int(b[i]) + int(b[len(b) - len(a) + i + 1]))
res = 0
for i in range(len(a)):
	if a[i] == '0':
		res += shift[i]
	else:
		res += len(b) - len(a) + 1 - shift[i]
print(res)


a = input()
b = input()
inv = len(b) - len(a) + 1
count = 0
for i in range(inv):
	count += int(b[i])
ans = 0
for i in range(len(a)):
	if a[i] == '1':
		ans += inv - count
	else:
		ans += count
	if i < len(a) - 1:
		count -= int(b[i])
		count += int(b[inv + i])
print(ans)


def main():
	(aa, bb, zz, oo) = (input(), input(), [0], [0])
	z = o = 0
	for c in bb:
		if c == '0':
			z += 1
		else:
			o += 1
		zz.append(z)
		oo.append(o)
	print(sum((oo[stop] - oo[start] if c == '0' else zz[stop] - zz[start] for (c, start, stop) in zip(aa, range(999999), range(len(bb) - len(aa) + 1, 999999)))))
main()


import math
import itertools
a = [int(x) for x in input().rstrip()]
b = [int(x) for x in input().rstrip()]
n = len(a)
m = len(b)
prefix_b = [0] + list(itertools.accumulate(b))
res = 0
for i in range(n):
	ones = prefix_b[-n + i] - prefix_b[i]
	res += m - n + 1 - ones if a[i] else ones
print(res)


a = input()
b = input()
l = len(a)
m = len(b)
init = 0
lent = m - l + 1
for i in range(lent):
	init += int(b[i])
array = [init]
for i in range(l - 1):
	init += int(b[i + lent]) - int(b[i])
	array.append(init)
s = 0
for i in range(l):
	if a[i] == '0':
		s += array[i]
	else:
		s += lent - array[i]
print(s)


def solve(a, b):
	dict_ = {}
	ones_count = 0
	for i in range(len(a) - len(b) + 1):
		if a[i] == '1':
			ones_count += 1
	dict_[0] = ones_count
	for i in range(1, len(b)):
		if a[i - 1] == '1':
			ones_count -= 1
		if a[len(a) - len(b) + i] == '1':
			ones_count += 1
		dict_[i] = ones_count
	sum_ = 0
	for i in range(len(b)):
		if b[i] == '0':
			sum_ += dict_[i]
		else:
			sum_ += len(a) - len(b) + 1 - dict_[i]
	return str(sum_)
b = input()
a = input()
print(solve(a, b))


from copy import copy
a = input()
b = input()
aa = len(a)
bb = len(b)
f = dict(zip([i for i in range(aa)], [0 for j in range(aa)]))
c = bb - aa

def brraw(b):
	global f
	for i in range(c + 1):
		if b[i] == '1':
			f[0] += 1
	for i in range(1, aa):
		f[i] = copy(f[i - 1])
		if b[i + c] == '1':
			f[i] += 1
		if b[i - 1] == '1':
			f[i] -= 1
brraw(b)
res = 0
for i in range(aa):
	if a[i] == '0':
		res += f[i]
	else:
		res += c + 1 - f[i]
print(res)


from sys import stdin
a = stdin.readline().strip()
b = stdin.readline().strip()
one = [0] * len(b)
zero = [0] * len(b)
if b[0] == '0':
	zero[0] += 1
else:
	one[0] += 1
for i in range(1, len(b)):
	zero[i] = zero[i - 1]
	one[i] = one[i - 1]
	if b[i] == '0':
		zero[i] += 1
	else:
		one[i] += 1
p = len(b) - len(a)
ans = 0
for i in range(len(a)):
	if i == 0:
		if a[i] == '1':
			ans += zero[i + p]
		else:
			ans += one[i + p]
	elif a[i] == '1':
		ans += zero[i + p] - zero[i - 1]
	else:
		ans += one[i + p] - one[i - 1]
print(ans)


def main():
	a = input()
	b = input()
	total_comparable = len(b) - len(a) + 1
	if total_comparable < 1:
		print(0)
		return
	cumulitive_one_b = [0] * len(b)
	for i in range(len(b)):
		if i != 0:
			cumulitive_one_b[i] += cumulitive_one_b[i - 1]
		if b[i] == '1':
			cumulitive_one_b[i] += 1
	hamming_distance = 0
	for i in range(len(a)):
		start = i
		end = i + total_comparable - 1
		if start == 0:
			total_comparable_one = cumulitive_one_b[end]
		else:
			total_comparable_one = cumulitive_one_b[end] - cumulitive_one_b[start - 1]
		if a[i] == '0':
			hamming_distance += total_comparable_one
		else:
			hamming_distance += total_comparable - total_comparable_one
	print(hamming_distance)
main()


a = input()
b = input()
cum_freq = [0]
if b[0] == '1':
	cum_freq[0] = 1
for i in range(1, len(b)):
	cum_freq.append(cum_freq[-1])
	if b[i] == '1':
		cum_freq[-1] += 1
overlap = 0
a_count = 0
if a[0] == '1':
	overlap += cum_freq[len(b) - len(a)]
	a_count += 1
for i in range(1, len(a)):
	if a[i] == '1':
		overlap += cum_freq[len(b) - len(a) + i] - cum_freq[i - 1]
		a_count += 1
b_count = cum_freq[len(a) - 1]
for i in range(len(a), len(b)):
	b_count += cum_freq[i] - cum_freq[i - len(a)]
print(a_count * (len(b) - len(a) + 1) + b_count - 2 * overlap)


a = str(input())
b = str(input())
count = 0
al = len(a)
bl = len(b)
s = b[:bl - al + 1].count('1')
for i in range(al - 1):
	if a[i] == '0':
		count += s
	else:
		count += bl - al + 1 - s
	s += int(b[bl - al + i + 1]) - int(b[i])
if a[-1] == '0':
	count += s
else:
	count += bl - al + 1 - s
print(count)


a = input()
b = input()
a_ones = [0 for i in range(len(a) + 2)]
a_zeros = [0 for i in range(len(a) + 2)]
counter1 = 0
counter0 = 0
total = 0
ones = 0
zeros = 0
la = len(a)
k = len(b) - la + 1
for i in range(la):
	if a[i] == '1':
		counter1 += 1
	else:
		counter0 += 1
	a_ones[i] = counter1
	a_zeros[i] = counter0
la -= 1
if len(a) * 2 <= len(b):
	for i in range(len(b)):
		if i < la:
			ones = a_ones[i]
			zeros = a_zeros[i]
			if b[i] == '0':
				total += ones
			else:
				total += zeros
		elif la <= i and i <= len(b) - la - 1:
			ones = a_ones[la]
			zeros = a_zeros[la]
			if b[i] == '0':
				total += ones
			else:
				total += zeros
		else:
			ones = a_ones[la] - a_ones[-len(b) + la + i]
			zeros = a_zeros[la] - a_zeros[-len(b) + la + i]
			if b[i] == '0':
				total += ones
			else:
				total += zeros
	print(total)
else:
	for i in range(len(b)):
		if i < len(b) - la - 1:
			ones = a_ones[i]
			zeros = a_zeros[i]
			if b[i] == '0':
				total += ones
			else:
				total += zeros
		elif i > la:
			ones = a_ones[la] - a_ones[-len(b) + la + i]
			zeros = a_zeros[la] - a_zeros[-len(b) + la + i]
			if b[i] == '0':
				total += ones
			else:
				total += zeros
		else:
			ones = a_ones[i + len(b) - la - k] - a_ones[i - k]
			zeros = a_zeros[i + len(b) - la - k] - a_zeros[i - k]
			if b[i] == '0':
				total += ones
			else:
				total += zeros
	print(total)


(a, b, f, g) = (input(), input(), [[0], [0]], lambda x: 0 if x == '1' else 1)
for i in b:
	f[0].append(f[0][-1] + (i == '0'))
	f[1].append(f[1][-1] + (i == '1'))
ans = sum([f[g(c)][len(b) - len(a) + i + 1] - f[g(c)][i] for (i, c) in enumerate(a)])
print(ans)


import os
import sys
from io import BytesIO, IOBase

def main():
	a = list(map(int, input()))
	b = list(map(int, input()))
	dff = len(b) - len(a)
	if dff < 0:
		print(0)
		exit()
	lb = len(b)
	c = [0] * (lb + 1)
	for i in range(lb):
		c[i + 1] = c[i] + b[i]
	ans = 0
	for i in range(len(a)):
		item = a[i]
		if item:
			ans += dff + 1 - (c[dff + i + 1] - c[i])
		else:
			ans += c[dff + i + 1] - c[i]
	print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


a = input().rstrip()
b = input().rstrip()
(n, m) = (len(a), len(b))
q = [0] * (m + 1)
for i in range(1, m + 1):
	q[i] = q[i - 1] + int(b[i - 1])
ans = 0
w = m - n + 1
for i in range(n):
	if a[i] == '0':
		ans += q[w + i] - q[i]
	else:
		ans += w - (q[w + i] - q[i])
print(ans)


a = input()
b = input()
(n, m) = (len(a), len(b))
res = 0
p = [[0] * (m + 1), [0] * (m + 1)]
for i in range(m):
	p[0][i + 1] = p[0][i] + int(b[i] == '0')
	p[1][i + 1] = p[1][i] + int(b[i] != '0')
for i in range(n):
	for j in range(2):
		res += abs(int(a[i] == '1') - j) * (p[j][m - n + i + 1] - p[j][i])
print(res)


a = input()
b = input()
a_len = len(a)
b_len = len(b)
temporary_sum = 0
hamming_sum = 0
for i in range(b_len - a_len + 1):
	temporary_sum += int(b[i])
hamming_sum += abs((b_len - a_len + 1) * int(a[0]) - temporary_sum)
for i in range(b_len - a_len + 1, b_len):
	temporary_sum += int(b[i]) - int(b[i - (b_len - a_len + 1)])
	hamming_sum += abs((b_len - a_len + 1) * int(a[i - (b_len - a_len + 1) + 1]) - temporary_sum)
print(hamming_sum)


a = input()
b = input()
sb = len(b)
sa = len(a)
pref1 = [0] * (sb + 1)
pref0 = [0] * (sb + 1)
for i in range(sb):
	pref1[i + 1] = pref1[i] + (b[i] == '1')
	pref0[i + 1] = pref0[i] + (b[i] == '0')
res = 0
end = sb - sa + 1
for i in range(sa):
	if a[i] == '1':
		l = i + 1
		r = i + end
		res += pref0[r] - pref0[l - 1]
	else:
		l = i + 1
		r = i + end
		res += pref1[r] - pref1[l - 1]
print(res)


import sys
a = input()
b = input()
sums = []
for i in range(len(b)):
	sums.append(ord(b[i]) - ord('0'))
	if len(sums) >= 2:
		sums[-1] += sums[-2]
ans = 0
for i in range(len(a)):
	onenum = sums[len(b) - len(a) + i]
	if i > 0:
		onenum -= sums[i - 1]
	if a[i] == '1':
		ans += len(b) - len(a) - onenum + 1
	else:
		ans += onenum
print(ans)


c = []
d = []
c.append(0)
d.append(0)
sum = 0
k = 0
l = 0
a = list(map(int, input()))
b = list(map(int, input()))
for i in range(len(b)):
	if b[i] == 0:
		k += 1
	else:
		l += 1
	c.append(k)
	d.append(l)
for j in range(len(a)):
	if a[j] == 0:
		sum += d[len(b) - len(a) + j + 1] - d[j]
	else:
		sum += c[len(b) - len(a) + j + 1] - c[j]
print(sum)


I = lambda : list(map(int, input().split()))
(s1, s2) = (input(), input())
(l1, l2) = (len(s1), len(s2))
(ans, units) = (0, 0)
dp = [0]
for i in range(l2):
	units += int(s2[i])
	dp.append(units)
for i in range(l1):
	if s1[i] == '0':
		ans += dp[l2 - l1 + i + 1] - dp[i]
	else:
		ans += l2 - l1 + 1 - dp[l2 - l1 + i + 1] + dp[i]
print(ans)


a = [int(x) for x in input()]
b = [int(x) for x in input()]
A = len(a)
B = len(b)
c = [[b[0] ^ 1] + [0] * (B - 1), [b[0]] + [0] * (B - 1)]
for i in range(1, B):
	c[0][i] = c[0][i - 1] + (b[i] ^ 1)
	c[1][i] = c[1][i - 1] + b[i]
ans = 0
for i in range(A):
	ans += c[a[i] ^ 1][i + B - A] - (c[a[i] ^ 1][i - 1] if i != 0 else 0)
print(ans)


def str_inp(n):
	return [stdin.readline()[:-1] for x in range(n)]

def arr_sum(arr):
	arr.appendleft(0)
	return list(accumulate(arr, lambda x, y: int(x) + int(y)))
from collections import *
from itertools import accumulate
from sys import stdin
(a, b) = str_inp(2)
(all, la, lb, ans) = (arr_sum(deque(a)), len(a), len(b), 0)
for i in range(la - 1, lb - la + 1):
	if int(b[i]):
		ans += la - all[-1]
	else:
		ans += all[-1]
for i in range(la - 1):
	if la + i > lb:
		break
	elif int(b[i]):
		ans += i + 1 - all[i + 1]
	else:
		ans += all[i + 1]
c = 2
for i in range(lb - la + 1, lb):
	if int(b[i]):
		ans += min(lb - i, lb - la + 1) - (all[c] - all[c - 1] + (all[min(la, c + (lb - la))] - all[c]))
	else:
		ans += all[c] - all[c - 1] + (all[min(la, c + (lb - la))] - all[c])
	c += 1
print(ans)


import sys
if False:
	inp = open('B.txt', 'r')
else:
	inp = sys.stdin
count = [0]
a = inp.readline().strip()
b = inp.readline().strip()
for i in range(len(b)):
	count.append(count[i] + int(b[i]))
lengthA = len(a)
lengthB = len(b)
ans = 0
for i in range(lengthA):
	if a[i] == '0':
		ans += count[lengthB + i - lengthA + 1] - count[i]
	else:
		ans += lengthB - lengthA + 1 - count[lengthB + i - lengthA + 1] + count[i]
print(ans)


def solve(a, b):
	m = len(a)
	n = len(b)
	p_b = [0]
	for x in b[:]:
		p_b.append(p_b[-1] + int(x))
	s = 0
	for i in range(m):
		if a[i] == '0':
			s += p_b[n - m + 1 + i] - p_b[i]
		else:
			s += n - m + 1 - (p_b[n - m + 1 + i] - p_b[i])
	return s
a = input()
b = input()
print(solve(a, b))


a = input()
b = input()
n = len(a)
m = len(b)
c = [[0] * (m + 1) for _ in range(2)]
for i in range(1, m + 1):
	t = int(b[i - 1])
	c[0][i] = c[0][i - 1] + abs(t)
	c[1][i] = c[1][i - 1] + abs(1 - t)
ans = 0
for i in range(1, n + 1):
	j = i + m - n
	t = int(a[i - 1])
	ans += c[t][j] - c[t][i - 1]
print(ans)


a = input()
b = input()
num_n = [0]
num_one = [0]
for elem in a:
	if elem == '1':
		num_one.append(num_one[-1] + 1)
		num_n.append(num_n[-1])
	else:
		num_one.append(num_one[-1])
		num_n.append(num_n[-1] + 1)
res = 0
la = len(a)
lb = len(b)
for i in range(lb):
	left = max(0, i - lb + la)
	right = min(la - 1, i)
	if b[i] == '1':
		res += num_n[right + 1] - num_n[left]
	else:
		res += num_one[right + 1] - num_one[left]
print(res)


a = input()
b = input()
sumi = 0
for i in range(len(b) - len(a) + 1):
	if b[i] == '1':
		sumi += 1
lowest = 0
highest = len(b) - len(a) + 1
total = 0
for i in range(len(a)):
	if a[i] == '0':
		total += sumi
	else:
		total += highest - lowest - sumi
	if b[lowest] == '1':
		sumi -= 1
	if highest < len(b) and b[highest] == '1':
		sumi += 1
	lowest += 1
	highest += 1
print(total)


a = input()
b = input()
c = 0
d = 0
e = len(b) - len(a) + 1
for i in range(len(b) - len(a) + 1):
	c += int(b[i])
for j in range(len(a)):
	f = int(a[j])
	if f == 1:
		d = d + e - c
	else:
		d = d + c
	if j == len(a) - 1:
		break
	c = c + int(b[e + j])
	c = c - int(b[j])
print(d)


a = [int(i) for i in input()]
b = [int(i) for i in input()]
p = [0, 0]
ds = {-1: [p[0], p[1]]}
(k, sm, La, Lb) = (0, 0, len(a), len(b))
for i in a:
	p[abs(i - 1)] += 1
	ds.update({k: [p[0], p[1]]})
	k += 1
for (i, j) in zip(range(Lb), b):
	xe = min(i, La - 1)
	xb = max(La - (Lb - i), 0)
	sm += ds[xe][j] - ds[xb - 1][j]
print(sm)


def main():
	a = input()
	b = input()
	len_a = len(a)
	len_b = len(b)
	num0 = [0 for _ in range(len_b)]
	num1 = [0 for _ in range(len_b)]
	for i in range(len_b):
		if b[i] == '0':
			num0[i] = 1
		else:
			num1[i] = 1
		if i > 0:
			num0[i] += num0[i - 1]
			num1[i] += num1[i - 1]
	ans = 0
	for i in range(len_a):
		if a[i] == '0':
			ans += num1[len_b - len_a + i]
			if i > 0:
				ans -= num1[i - 1]
		if a[i] == '1':
			ans += num0[len_b - len_a + i]
			if i > 0:
				ans -= num0[i - 1]
	print(ans)
main()


import sys
input = sys.stdin.readline
MOD = 1000000007
MOD2 = 998244353
ii = lambda : int(input().strip('\n'))
si = lambda : input().strip('\n')
dgl = lambda : list(map(int, input().strip('\n')))
f = lambda : map(int, input().strip('\n').split())
il = lambda : list(map(int, input().strip('\n').split()))
ls = lambda : list(input().strip('\n'))
lsi = lambda : [int(i) for i in ls()]
let = 'abcdefghijklmnopqrstuvwxyz'
for _ in range(1):
	a = lsi()
	b = lsi()
	an = len(a)
	bn = len(b)
	suf1 = [[0, 0] for i in range(an + 1)]
	for i in range(1, an + 1):
		suf1[i][a[i - 1]] = suf1[i - 1][a[i - 1]] + 1
		suf1[i][a[i - 1] ^ 1] = suf1[i - 1][a[i - 1] ^ 1]
	ans = 0
	it = 1
	for i in range(bn):
		it2 = max(it - (bn - max(an, i + 1)), 1)
		zer = suf1[it][0] - suf1[it2 - 1][0]
		one = suf1[it][1] - suf1[it2 - 1][1]
		ans += b[i] * zer + abs(b[i] - 1) * one
		it = min(it + 1, an)
	print(ans)


p = input()
s = input()
n = len(s)
ans = 0
dl = len(s) - len(p)
m = [(0, 0), (0, 1)] if s[0] == '1' else [(0, 0), (1, 0)]
for i in range(1, n):
	if s[i] == '0':
		m.append((m[-1][0] + 1, m[-1][1]))
	else:
		m.append((m[-1][0], m[-1][1] + 1))
for i in range(len(p)):
	if p[i] == '0':
		ans += m[dl + i + 1][1] - m[i][1]
	else:
		ans += m[dl + i + 1][0] - m[i][0]
print(ans)


a = input()
b = input()
c = [0]
s = 0
ans = 0
for i in range(len(b)):
	s += int(b[i])
	c.append(s)
x = len(b) - len(a) + 1
for i in range(len(a)):
	if a[i] == '0':
		ans += c[x + i] - c[i]
	else:
		ans += x - c[x + i] + c[i]
print(ans)


import sys
input = sys.stdin.readline
a = input()
b = input()
na = len(a)
nb = len(b)
c = 0
d = 0
e = [[0, 0]]
for i in range(nb):
	if b[i] == '0':
		c += 1
	else:
		d += 1
	e.append([c, d])
s = 0
for i in range(na):
	if a[i] == '0':
		s += e[i + nb - na + 1][1] - e[i][1]
	elif a[i] == '1':
		s += e[i + nb - na + 1][0] - e[i][0]
print(s)


from collections import Counter
(a, b, c, s) = (input(), input(), Counter(), 0)
k = len(b) - len(a) + 1
c[0] = b.count('0', 0, k)
for i in range(1, len(a)):
	c[i] = (b[i + k - 1] == '0') - (b[i - 1] == '0') + c[i - 1]
for i in range(len(a)):
	s += [c[i], k - c[i]][a[i] == '0']
print(s)


a = input()
b = input()
n = len(b) - len(a) + 1
c = []
c.append(b[:n].count('1'))
for i in range(len(a) - 1):
	ci = c[-1] + int(b[n + i]) - int(b[i])
	c.append(ci)
sol = 0
for (i, ai) in enumerate(a):
	if ai == '0':
		sol += c[i]
	else:
		sol += n - c[i]
print(sol)


a = input()
b = input()
A = len(a)
B = len(b)
d = B - A + 1
l = [-1] * A
count = 0
for i in range(d):
	if b[i] == '1':
		count += 1
l[0] = count
c = 0
for i in range(d, B):
	if b[i] == '1':
		count += 1
	if b[c] == '1':
		count -= 1
	c += 1
	l[c] = count
net = 0
for i in range(A):
	if a[i] == '0':
		net += l[i]
	else:
		net += d - l[i]
print(net)


a = list(map(int, input()))
b = list(map(int, input()))
s = 0
l = len(b)
if len(a) == len(b):
	for i in range(l):
		s += abs(a[i] - b[i])
	print(s)
	exit(0)
l = len(b)
m = len(a)
j = k = 0
c = [0]
d = [0]
for i in range(l):
	if b[i] == 0:
		j += 1
	if b[i] == 1:
		k += 1
	c.append(j)
	d.append(k)
for i in range(m):
	if a[i] == 0:
		s += d[l - m + i + 1] - d[i]
	else:
		s += c[l - m + i + 1] - c[i]
print(s)


from sys import stdin, stdout
mod = 10 ** 9 + 7
t = 1
for _ in range(t):
	a = input()
	b = input()
	n = len(a)
	m = len(b)
	dp = [[0 for i in range(2)] for j in range(m + 1)]
	dp[1][0] = int(b[0]) ^ 1
	dp[1][1] = int(b[0])
	for i in range(2, m + 1):
		dp[i][0] = dp[i - 1][0] + (int(b[i - 1]) ^ 1)
		dp[i][1] = dp[i - 1][1] + int(b[i - 1])
	ans = 0
	for i in range(n):
		count0 = dp[m - n + i + 1][0] - dp[i][0]
		count1 = dp[m - n + i + 1][1] - dp[i][1]
		ans += count0 * int(a[i]) + count1 * (int(a[i]) ^ 1)
	print(ans)


a = [int(c) for c in str(input())]
b = [int(c) for c in str(input())]
b_len = len(b)
a_len = len(a)
carCountPrefix = [[0 for c in range(2)] for _ in range(b_len + 1)]
b_zero_count = 0
b_one_count = 0
for b_i in range(b_len):
	if b[b_i] == 0:
		b_zero_count += 1
	elif b[b_i] == 1:
		b_one_count += 1
	carCountPrefix[b_i + 1][1] = b_one_count
	carCountPrefix[b_i + 1][0] = b_zero_count
res = 0
for cur in range(0, a_len):
	for dig in range(2):
		res += (carCountPrefix[b_len - a_len + cur + 1][dig] - carCountPrefix[cur][dig]) * abs(a[cur] - dig)
print(res)