Xenia is an amateur programmer. Today on the IT lesson she learned about the Hamming distance.

The Hamming distance between two strings s = s1s2... sn and t = t1t2... tn of equal length n is value <image>. Record [si ≠ ti] is the Iverson notation and represents the following: if si ≠ ti, 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, <image>. 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.

Input

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.

Output

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.

Examples

Input

100 10
a
aaaaaaaaaa


Output

0


Input

1 1
abacaba
abzczzz


Output

4


Input

2 3
rzr
az


Output

5

Note

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.
import java.io.*;
import java.util.*;

public class B implements Runnable{
	public static void main (String[] args) {new Thread(null, new B(), "_cf", 1 << 28).start();}

	public void run() {
		DeoxysS fs = new DeoxysS();
		PrintWriter out = new PrintWriter(System.out);
		System.err.println("Go!");

		long[] vs = new long[2];
		vs[0] = fs.nextLong(); vs[1] = fs.nextLong();
		String[] ss = new String[2];
		ss[0] = fs.next(); ss[1] = fs.next();
		
		if(ss[0].length() < ss[1].length()) {
			String s = ss[0]; ss[0] = ss[1]; ss[1] = s;
			vs[0] = vs[0] ^ vs[1] ^ (vs[1] = vs[0]);
		}

		int n = ss[0].length(), m = ss[1].length();
		int gcd = (int)gcd(n, m);
		long lcm = lcm(n, m);
		int cLen = (int)(lcm / m);
		int[][] freq = new int[26][gcd];
		for(int i = 0; i < gcd; i++) {
			for(int j = i, len = 0; len < cLen; j += gcd, len++) {
				freq[ss[0].charAt(j)-'a'][i]++;
			}
		}
		int[] sum = new int[gcd];
		for(int i = 0; i < gcd; i++)
			for(int j = 0; j < 26; j++)
				sum[i] += freq[j][i];
		long ham = 0;
		for(int i = 0; i < gcd; i++) {
			for(int j = i; j < m; j += gcd) {
				ham += sum[i] - freq[ss[1].charAt(j)-'a'][i];
			}
		}
		long num = (vs[0]*n) / lcm;
		long res = ham * num;
		out.println(res);

		out.close();
	}

	long gcd (int a, int b) {
		while(b > 0) {
			int temp = b;
			b = a % b;
			a = temp;
		}
		return a;
	}

	long lcm (int a, int b) {
		return (long)a * ((long)b / gcd(a, b));
	}

	class DeoxysS {
		public int BS = 1<<16;
		public char NC = (char)0;
		byte[] buf = new byte[BS];
		int bId = 0, size = 0;
		char c = NC;
		double num = 1;
		BufferedInputStream in;

		public DeoxysS() {
			in = new BufferedInputStream(System.in, BS);
		}

		public DeoxysS(String s) throws FileNotFoundException {
			in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
		}

		public char nextChar(){
			while(bId==size) {
				try {
					size = in.read(buf);
				}catch(Exception e) {
					return NC;
				}                
				if(size==-1)return NC;
				bId=0;
			}
			return (char)buf[bId++];
		}

		public int nextInt() {
			return (int)nextLong();
		}

		public long nextLong() {
			num=1;
			boolean neg = false;
			if(c==NC)c=nextChar();
			for(;(c<'0' || c>'9'); c = nextChar()) {
				if(c=='-')neg=true;
			}
			long res = 0;
			for(; c>='0' && c <='9'; c=nextChar()) {
				res = (res<<3)+(res<<1)+c-'0';
				num*=10;
			}
			return neg?-res:res;
		}

		public double nextDouble() {
			double cur = nextLong();
			return c!='.' ? cur:cur+nextLong()/num;
		}

		public String next() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c>32) {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public String nextLine() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c!='\n') {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public boolean hasNext() {
			if(c>32)return true;
			while(true) {
				c=nextChar();
				if(c==NC)return false;
				else if(c>32)return true;
			}
		}
		
		public int[] nextIntArray(int n) {
			int[] res = new int[n];
			for(int i = 0; i < n; i++) res[i] = nextInt();
			return res;
		}
		
	}

}