CF356B.Xenia and Hamming

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.

泽尼亚是一名业余程序员。今天的信息技术课上，她学习了汉明距离的概念。

两个等长为 $n$ 的字符串 $s = s_1 s_2 \dots s_n$ 和 $t = t_1 t_2 \dots t_n$ 之间的汉明距离定义为值 。其中记号 $[s_i \ne t_i]$ 是艾弗森括号记法，其含义如下：若 $s_i \ne t_i$，则值为 $1$；否则为 $0$。

现在泽尼亚希望计算两个长字符串 $a$ 和 $b$ 之间的汉明距离。第一个字符串 $a$ 是由 $n$ 个字符串 $x$ 拼接而成，即 $a = \underbrace{x x \dots x}_{n\text{ 个 }x}$，如图所示：。第二个字符串 $b$ 是由 $m$ 个字符串 $y$ 拼接而成。

请帮助泽尼亚，在给定 $n$、$x$、$m$、$y$ 的情况下，计算所需的汉明距离。

The first line contains two integers n and m (1 ≤ n, m ≤ 1012). The second line contains a non-empty string x. The third line contains a non-empty string y. Both strings consist of at most 106 lowercase English letters.

It is guaranteed that strings a and b that you obtain from the input have the same length.

第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 10^{12}$）。
第二行包含一个非空字符串 $x$。
第三行包含一个非空字符串 $y$。
两个字符串均由至多 $10^6$ 个小写英文字母组成。

保证由输入得到的字符串 $a$ 和 $b$ 长度相同。

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.

输出一个整数——所需的汉明距离。

请注意，在 C++ 中读取或写入 64 位整数时，请勿使用 %lld 说明符。推荐使用 cin、cout 流，或 %I64d 说明符。

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$ 与字符串 $b$ 相同，均为由 100 个字母 a 组成的字符串。由于两个字符串完全相等，它们之间的汉明距离为零。

在第二个测试用例中，字符串 $a$ 与字符串 $b$ 在第 3、第 5、第 6 和第 7 个字符处不同。因此，汉明距离等于 4。

在第三个测试用例中，字符串 $a$ 为 rzrrzr，字符串 $b$ 为 azazaz。这两个字符串除第二个字符外，其余所有字符均不同，因此它们之间的汉明距离等于 5。