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

The first line contains two integers $ n $ and $ m $ $ (1

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.