Tổng khoảng cách Hamming

Khoảng cách Hamming giữa hai xâu nhị phân $s$ và $t$ có cùng độ dài được định nghĩa là

$$d(s,t)=\sum _{i=1}^{|s|}|s_i-t_i|,$$

trong đó $s_i$, $t_i$ là ký tự thứ $i$ của $s$ và $t$ (được xem như chữ số $0$ hoặc $1$). Nói cách khác, đó là số vị trí mà hai xâu khác nhau.

Cho hai xâu nhị phân $a$ và $b$ với $|a|\le |b|$. Hãy tính tổng khoảng cách Hamming giữa $a$ và tất cả các xâu con liên tiếp của $b$ có độ dài $|a|$.

Các xâu con liên tiếp được đếm theo vị trí xuất hiện: nếu hai xâu con ở hai vị trí khác nhau mà giống hệt nhau thì vẫn được tính hai lần. Tổng cộng có đúng $|b|-|a|+1$ xâu con cần xét.

Dữ liệu vào

• Dòng đầu tiên chứa xâu nhị phân $a$.
• Dòng thứ hai chứa xâu nhị phân $b$.

Dữ liệu ra

Một số nguyên duy nhất: tổng khoảng cách Hamming cần tìm.

Ràng buộc

• $1\le |a|\le 200000$
• $|a|\le |b|\le 200000$
• $a$ và $b$ chỉ gồm các ký tự '0' và '1'.

Ví dụ