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;
using ll = long long;
const int C = 400001, MAX_ORD = 101;
int check_element(int x, vector<int>& system, int M) {
  int r = 1, ln = system.size(), res = 0, i;
  for (i = 0; i < ln; i++) {
    res = (res + 1ll * (system[i] % M) * r) % M;
    r = (1ll * r * x) % M;
  }
  return res;
}
inline ll pow(ll a, ll b, ll M) {
  if (b == 0) return 1;
  ll c = 1;
  while (b > 0) {
    if (b % 2 == 1) c = (c * a) % M;
    b /= 2;
    a = (a * a) % M;
  }
  return c;
}
ll sum_order[C];
vector<vector<int> > divs(C), summa(C), elems(C);
int dv[C][10], ln[C], toth[C], primes[C];
int prob_primitive_root(int mod, int toth, int starter, int dv[], int ln) {
  int i;
  ll g, d = 1ll * RAND_MAX + 1;
  while (1) {
    g = (rand() * d + rand()) % mod;
    if (g % starter == 0) continue;
    for (i = 0; i < ln; i++) {
      if (pow(g, toth / dv[i], mod) == 1) break;
    }
    if (i == ln) break;
  }
  return g;
}
std::pair<int, int> ord_list[C];
int found[C], n_ord = 0;
void calc_orders(vector<vector<int> >& divs, int M) {
  int i, j, ij, jj, x, pw_tmp, pw_base;
  n_ord = 0;
  x = prob_primitive_root(M, M - 1, M, dv[M - 1], ln[M - 1]);
  j = M - 1;
  for (ij = divs[j].size() - 1; ij >= 0; ij--) {
    if (j / divs[j][ij] >= MAX_ORD) break;
    pw_base = pow(x, divs[j][ij], M);
    pw_tmp = pw_base;
    for (jj = divs[j][ij] - 1; jj < j; jj += divs[j][ij]) {
      if (found[pw_tmp] < M) {
        found[pw_tmp] = M;
        ord_list[n_ord] = {pw_tmp, j / divs[j][ij]};
        n_ord++;
      }
      pw_tmp = (1ll * pw_tmp * pw_base) % M;
    }
  }
}
int h2[2 * C], ih = 1;
ll h[2 * C];
void pop() {
  h[1] = h[ih - 1], h2[1] = h2[ih - 1], ih--;
  int j = 1;
  ll c;
  while (j < ih) {
    if (j * 2 < ih && h[j * 2] < h[j] &&
        (h[j * 2 + 1] >= h[j * 2] || j * 2 + 1 >= ih))
      c = h[j], h[j] = h[j * 2], h[j * 2] = c, c = h2[j], h2[j] = h2[j * 2],
      h2[j * 2] = c, j = j * 2;
    else if (j * 2 + 1 < ih && h[j * 2 + 1] < h[j])
      c = h[j], h[j] = h[j * 2 + 1], h[j * 2 + 1] = c, c = h2[j],
      h2[j] = h2[j * 2 + 1], h2[j * 2 + 1] = c, j = j * 2 + 1;
    else
      break;
  }
}
void push(ll a, int v) {
  h[ih] = a, h2[ih] = v, ih++;
  int j = ih - 1;
  ll c;
  while (j > 1) {
    if (h[j / 2] > h[j])
      c = h[j], h[j] = h[j / 2], h[j / 2] = c, c = h2[j], h2[j] = h2[j / 2],
      h2[j / 2] = c, j /= 2;
    else
      break;
  }
}
int main() {
  srand(time(NULL));
  int p, r, i, j, ij, jj, n, m, minn = -1, M, testo = 0;
  string a, b;
  toth[1] = 1;
  for (i = 2; i < C; i++) primes[i] = 1, toth[i] = i;
  for (i = 2; i < C; i++) {
    if (primes[i] == 0) continue;
    for (j = i; j < C; j += i) {
      if (j != i) primes[j] = 0;
      toth[j] = (toth[j] / i) * (i - 1);
      dv[j][ln[j]] = i, ln[j]++;
    }
  }
  for (i = 1; i < C; i++) {
    for (j = i; j < C; j += i) {
      divs[j].push_back(i);
      sum_order[j] += 1ll * (j / i) * toth[j / i];
    }
  }
  scanf("%d %d", &n, &m);
  cin >> a >> b;
  int calcs = 0;
  for (j = m + 1; j < C; j++) {
    if (primes[j] == 1) push(sum_order[j - 1], j);
  }
  for (i = 1; i < MAX_ORD; i++) {
    elems[i].reserve(i);
    for (j = 0; j < i; j++) {
      elems[i].push_back(0);
      for (ij = j; ij < n; ij += i) {
        elems[i][j] = elems[i][j] + a[ij] - b[ij];
      }
    }
  }
  while (ih > 0) {
    calcs++;
    M = h2[1];
    pop();
    calc_orders(divs, M);
    for (i = 0; i < n_ord; i++) {
      if (ord_list[i].first == 1 || ord_list[i].first == M - 1) continue;
      testo = check_element(ord_list[i].first, elems[ord_list[i].second], M);
      if (!testo) break;
    }
    if (!testo) break;
  }
  printf("%d %d\n", M, ord_list[i].first);
  return 0;
}
