Ксюша — начинающий программист. Сегодня на паре по программированию она изучила, что такое расстояние Хемминга.
Расстоянием Хемминга между двумя строками s = s1s2... sn и t = t1t2... tn равной длины n называется величина 
. Запись [si ≠ ti] является нотацией Айверсона и обозначает: если si ≠ ti — единицу, иначе — ноль.
Теперь Ксюша хочет посчитать расстояние Хемминга между двумя длинными строками a и b. Первая строка a — это конкатенация n копий строки x, то есть 
. Вторая строка b — это конкатенация m копий строки y.
Помогите Ксюше, вычислите требуемое расстояние Хемминга по заданным n, x, m, y.
Выходные данные
Выведите единственное целое число — искомое расстояние Хемминга.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
Примечание
В первом тестовом примере строка a равна строке b и равна 100 буквам a. Так как строки равны, расстояние Хемминга между ними равно нулю.
Во втором тестовом примере у строк a и b различаются 3-ый, 5-ый, 6-ой, и 7-ой символы. Таким образом расстояние Хемминга равно 4.
В третьем тестовом примере строка a равна rzrrzr, а строка b — azazaz. Строки отличаются во всех символах кроме 2-го, расстояние Хемминга между ними равно 5.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
100 10
a
aaaaaaaaaa
|
0
|
|
2
|
1 1
abacaba
abzczzz
|
4
|
|
3
|
2 3
rzr
az
|
5
|