Yo`nalishlar
Hozirda online

Statistika

Masalalar soni: 909

Foydalanuvchilar soni: 8825

Jo'natishlar soni: 714634

Muhokama yozuvlari: 4541

Yangiliklar soni: 98

Yangiliklar izohlari: 1179


So'ngi izohlar

799. Hamming distance
Vaqt limiti: 1 sekund
Xotira limiti: 64 MB

Описание: http://1.bp.blogspot.com/_QsIsbT1SW1I/SwqGC_zpEBI/AAAAAAAAANg/Y4ZSRrWHZb8/s200/richard_hamming4.jpg

Richard Hemming

In information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different. In another way, it measures the minimum number of substitutions required to change one string into the other, or the minimum number of errors that could have transformed one string into the other. Let us define Hamming distance as d(s1, s2). For example: d(tatuuf, tuitub)= 4, d(more, code)=2, d(algo, algo)=0. In this problem you are given two strings s and t. Your task is to calculate the sum of Hamming distances beetween t and all substrings of s.

Input

In the first line given s , in the secont given t. Both strings contain lowercase english letters (1≤|t|≤|s|≤106). |x| - the length of string x.

Output

Output the answer to problem.

Examples

Input

Output

1

azat

ozod

3

2

abdavcaeaada

abda

24

 

Avtor: Azat Yusupov
2015 yil Dasturlash bo'yicha Tatu va uning filiallari talabalari o'rtasida jamoaviy olimpiada. Final. Urgench 21-23 aprel.
Mening urinishlarim(0) Muhokama (4) Jo'natish Eng yaxshi yechimlar Barcha muvaffaqiyatli urinishlar(12) Barcha urinishlar(66)