Hamming Distance

Limits 1s, 512 MB

Hamming distance between two binary strings of equal length is the number of mismatches between every corresponding positions of the two strings.
Suppose A = “01001” and B = “11000” then the Hamming Distance between A and B is 2 because they only mismatch in position 1 and 5 (1- based indexing).

Now, you are given two string A and B of length n and m respectively. A and B contains only lowercase english letters.
You have to calculate the sum of hamming distance between every substring of length m of A and B

Input

The first line will contain two integers’ n and m.
Then the second line will contain two strings, A of length n and B of length m.
1 <= n,m <= 106

Output

A single integer, the sum of hamming distance between every substring of length m of A and B .

Sample

Input	Output
5 3 ababa aba	3
In the first sample case, HD(“aba, aba”) = 0, HD(“bab”, “aba”) = 3, HD(“aba”, ”aba”) = 0. So the answer is 0 + 3 + 0 = 3. Note: HD = Hamming Distance.

Input

Output

5 3
ababa aba

In the first sample case, HD(“aba, aba”) = 0, HD(“bab”, “aba”) = 3, HD(“aba”, ”aba”) = 0.
So the answer is 0 + 3 + 0 = 3.

Note: HD = Hamming Distance.