Xenia 是一位业余程序员。今天在 IT 课上她学到了汉明距离。
长度相等的两个字符串 s = s1s2... sn 和 t = t1t2... tn 之间的汉明距离值为 $$\sum_{i=1}^{n}[s_i \neq t_i]$$。记录 [si ≠ ti] 是艾弗森符号,表示如下:如果 si ≠ ti,则为 1,否则为 0。
现在 Xenia 想要计算两个长字符串 a 和 b 之间的汉明距离。第一个字符串 a 是字符串 x 的 n 个副本的串联,即 $$a = x + x + \cdots + x = \sum_{i=1}^{n} x$$。第二个字符串 b 是字符串 y 的 m 个副本的串联。
帮助 Xenia,计算所需的汉明距离,给定 n、x、m、y。
输入
第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 1012)。第二行包含一个非空字符串 x。第三行包含一个非空字符串 y。这两个字符串最多由 106 个小写英文字母组成。
保证从输入中获得的字符串 a 和 b 具有相同的长度。
输出
打印一个整数 - 所需的汉明距离。
请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。
示例
输入 #1
100 10 a aaaaaaaaaa
输出 #1
0
输入 #2
1 1 abacaba abzczzz
输出 #2
4
输入 #3
2 3 rzr az
输出 #3
5
注意
在第一个测试用例中,字符串 a 与字符串 b 相同,并且等于 100 个字母 a。由于两个字符串相等,因此它们之间的汉明距离为零。
在第二个测试用例中,字符串 a 和 b 的第 3 个、第 5 个、第 6 个和第 7 个字符不同。因此,汉明距离等于 4。
在第三个测试用例中,字符串 a 是 rzrrzr,字符串 b 是 azazaz。除了第二个字符串之外,字符串的所有字符都不同,它们之间的汉明距离等于 5。