A9234. 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$ .

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.

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.