Xenia and Hamming

题意翻译

计算字符串 $a$ 的 $n$ 次循环和字符串 $b$ 的 $m$ 次循环中对应字符不同的个数（ Hamming distance）。数据保证最后两个字符串等长。 $n,m \leq 10^{12}$，$len(a ),len(b)\leq 10^6$

题目描述

Xenia is an amateur programmer. Today on the IT lesson she learned about the Hamming distance. The Hamming distance between two strings $ s=s_{1}s_{2}...\ s_{n} $ and $ t=t_{1}t_{2}...\ t_{n} $ of equal length $ n $ is value . Record $ [s_{i}≠t_{i}] $ is the Iverson notation and represents the following: if $ s_{i}≠t_{i} $ , it is one, otherwise — zero. Now Xenia wants to calculate the Hamming distance between two long strings $ a $ and $ b $ . The first string $ a $ is the concatenation of $ n $ copies of string $ x $ , that is, . The second string $ b $ is the concatenation of $ m $ copies of string $ y $ . Help Xenia, calculate the required Hamming distance, given $ n,x,m,y $ .

输入输出格式

输入格式

The first line contains two integers $ n $ and $ m $ $ (1<=n,m<=10^{12}) $ . The second line contains a non-empty string $ x $ . The third line contains a non-empty string $ y $ . Both strings consist of at most $ 10^{6} $ lowercase English letters. It is guaranteed that strings $ a $ and $ b $ that you obtain from the input have the same length.

输出格式

Print a single integer — the required Hamming distance. Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

输入输出样例

输入样例 #1

100 10
a
aaaaaaaaaa

输出样例 #1

0

输入样例 #2

1 1
abacaba
abzczzz

输出样例 #2

4

输入样例 #3

2 3
rzr
az

输出样例 #3

5

说明

In the first test case string $ a $ is the same as string $ b $ and equals 100 letters a. As both strings are equal, the Hamming distance between them is zero. In the second test case strings $ a $ and $ b $ differ in their 3-rd, 5-th, 6-th and 7-th characters. Thus, the Hamming distance equals 4. In the third test case string $ a $ is rzrrzr and string $ b $ is azazaz. The strings differ in all characters apart for the second one, the Hamming distance between them equals 5.

题意翻译

计算字符串 $a$ 的 $n$ 次循环和字符串 $b$ 的 $m$ 次循环中对应字符不同的个数（ Hamming distance）。数据保证最后两个字符串等长。 $n,m \leq 10^{12}$，$len(a ),len(b)\leq 10^6$