Now Heidi is ready to crack Madame Kovarian's hashing function.

Madame Kovarian has a very strict set of rules for name changes. Two names can be interchanged only if using the following hashing function on them results in a collision. However, the hashing function is parametrized, so one can always find a set of parameters that causes such a collision. Heidi decided to exploit this to her advantage.

Given two strings w_1, w_2 of equal length n consisting of lowercase English letters and an integer m.

Consider the standard polynomial hashing function:

H_p(w) := \left( ∑_{i=0}^{|w|-1} w_i r^i \right) \mbox{mod}(p)

where p is some prime, and r is some number such that 2≤ r ≤ p-2.

The goal is to find r and a prime p (m ≤ p ≤ 10^9) such that H_p(w_1) = H_p(w_2).

Strings w_1 and w_2 are sampled independently at random from all strings of length n over lowercase English letters.

Input

The first line contains two integers n and m (10 ≤ n ≤ 10^5, 2 ≤ m ≤ 10^5).

The second and the third line, respectively, contain the words w_1, w_2 that were sampled independently at random from all strings of length n over lowercase English letters.

Output

Output integers p, r.

p should be a prime in the range [m, 10^9] and r should be an integer satisfying r∈ [2,p-2].

At least one solution is guaranteed to exist. In case multiple solutions exist, print any of them.

Examples

Input


10 5
bgcbaaaaaa
cccaaaaaaa


Output


5 2

Input


10 100
melodypond
riversongg


Output


118219 79724

Note

In the first example, note that even though p=3 and r=2 also causes a colision of hashes, it is not a correct solution, since m is 5 and thus we want p≥ 5.

In the second example, we are aware of the extra 'g' at the end. We just didn't realize that "River Song" and "Melody Pond" have different lengths...
#include <bits/stdc++.h>
using namespace std;
long long mod(long long a, long long m) { return ((a % m) + m) % m; }
int extended_euclid(int a, int b, int &x, int &y) {
  int xx = y = 0;
  int yy = x = 1;
  while (b) {
    int q = a / b;
    int t = b;
    b = a % b;
    a = t;
    t = xx;
    xx = x - q * xx;
    x = t;
    t = yy;
    yy = y - q * yy;
    y = t;
  }
  return a;
}
int mod_inverse(int a, int n) {
  int x, y;
  int d = extended_euclid(a, n, x, y);
  if (d > 1) return -1;
  return mod(x, n);
}
long long powmod(long long a, long long b, long long m) {
  long long res = 1;
  while (b > 0)
    if (b & 1)
      res = (res * a) % m, --b;
    else
      a = (a * a) % m, b >>= 1;
  return res % m;
}
bool Miller(long long p, long long s, int a) {
  if (p == a) return 1;
  long long mod = powmod(a, s, p);
  for (; s - p + 1 && mod - 1 && mod - p + 1; s *= 2) mod = (mod * mod) % p;
  return mod == p - 1 || s % 2;
}
bool isprime(long long n) {
  if (n < 2) return 0;
  if (n % 2 == 0) return n == 2;
  long long s = n - 1;
  while (s % 2 == 0) s /= 2;
  return Miller(n, s, 2) && Miller(n, s, 7) && Miller(n, s, 61);
}
long long gcd(long long a, long long b) {
  long long tmp;
  while (b) {
    a %= b;
    tmp = a;
    a = b;
    b = tmp;
  }
  return a;
}
int primitive_root(int m) {
  int phi = m - 1;
  int n = phi;
  vector<int> fact;
  for (int i = 2; i * i <= n; ++i)
    if (n % i == 0) {
      fact.push_back(i);
      while (n % i == 0) n /= i;
    }
  if (n > 1) fact.push_back(n);
  for (int res = 2; res < m; ++res) {
    if (gcd(res, m) != 1) continue;
    bool ok = true;
    for (int f : fact)
      if (powmod(res, phi / f, m) == 1) {
        ok = false;
        break;
      }
    if (ok) return res;
  }
  return -1;
}
int MOD = 998244353;
int root = 565042129;
int root_pw = 1 << 20;
int root_1 = mod_inverse(root, MOD);
void fft(vector<int> &a, bool invert) {
  int n = a.size();
  for (int i = 1, j = 0; i < n; i++) {
    int bit = n >> 1;
    for (; j & bit; bit >>= 1) j ^= bit;
    j ^= bit;
    if (i < j) swap(a[i], a[j]);
  }
  for (int len = 2; len <= n; len <<= 1) {
    int wlen = invert ? root_1 : root;
    for (int i = len; i < root_pw; i <<= 1)
      wlen = (int)(1LL * wlen * wlen % MOD);
    for (int i = 0; i < n; i += len) {
      int w = 1;
      for (int j = 0; j < len / 2; j++) {
        int u = a[i + j], v = (int)(1LL * a[i + j + len / 2] * w % MOD);
        a[i + j] = u + v < MOD ? u + v : u + v - MOD;
        a[i + j + len / 2] = u - v >= 0 ? u - v : u - v + MOD;
        w = (int)(1LL * w * wlen % MOD);
      }
    }
  }
  if (invert) {
    int n_1 = mod_inverse(n, MOD);
    for (int &x : a) x = (int)(1LL * x * n_1 % MOD);
  }
}
vector<int> f;
vector<int> ntt(vector<int> &poly, int offset = 0, int dist = 1, int fp = 0) {
  vector<int> ans;
  if (dist == root_pw) {
    ans.push_back(poly[offset]);
  } else {
    int d = f[fp];
    vector<vector<int> > D;
    for (int i = 0; i < d; ++i) {
      D.push_back(ntt(poly, offset + dist * i, dist * d, fp + 1));
    }
    for (int i = 0; i * dist < root_pw; ++i) {
      int x = powmod(root, i * dist, MOD);
      int idx = i % (root_pw / (d * dist));
      long long y = 0;
      for (int j = 0; j < d; ++j) {
        y = (y + (long long)powmod(x, j, MOD) * D[j][idx]) % MOD;
      }
      ans.push_back(y);
    }
  }
  return ans;
}
int main() {
  ios_base::sync_with_stdio(false);
  cout << setprecision(12) << fixed;
  int n, m;
  string w1, w2;
  cin >> n >> m >> w1 >> w2;
  int cnt = 0;
  for (int B = max(m - 1, n);; ++B) {
    long long p = B + 1;
    if (!isprime(p)) continue;
    int pp = B;
    f.clear();
    for (int i = 2; i * i <= pp; ++i) {
      while (pp % i == 0) {
        pp /= i;
        f.push_back(i);
      }
    }
    if (pp > 1) f.push_back(pp);
    if (f.back() > 19) continue;
    int pr = primitive_root(p);
    MOD = p;
    root = pr;
    root_pw = B;
    root_1 = mod_inverse(root, MOD);
    vector<int> a(B, 0);
    for (int i = 0; i < n; ++i) {
      a[i] = mod(w1[i] - w2[i], p);
    }
    a = ntt(a);
    for (int i = 0; i < B; ++i) {
      if (a[i] == 0) {
        int val = powmod(root, i, p);
        if (val > 1 && val < p - 1) {
          cout << p << " " << val << endl;
          return 0;
        }
      }
    }
    ++cnt;
  }
  cout << cnt << endl;
  return 1;
}
