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;
const int N = 1e6 + 10;
int n, m, pr[N], cnt, w[233], ccc;
bool ip[N];
vector<int> f[233];
char s[N], t[N];
void sieve(int n) {
  memset(ip, 1, sizeof(ip));
  ip[1] = 0;
  for (int i = (2); i <= (n); ++i) {
    if (ip[i]) pr[++cnt] = i;
    for (int j = 1; j <= cnt && i * pr[j] <= n; ++j) {
      ip[i * pr[j]] = 0;
      if (i % pr[j] == 0) break;
    }
  }
  for (int i = (2); i <= (40); ++i)
    for (int j = (1); j <= (cnt); ++j)
      if (pr[j] > m && pr[j] % pr[i] == 1) f[i].push_back(pr[j]);
}
int ksm(int a, int b, int p) {
  int ans = 1;
  for (; b; b >>= 1, a = 1ll * a * a % p)
    if (b & 1) ans = 1ll * ans * a % p;
  return ans;
}
int main() {
  mt19937 rd;
  uniform_int_distribution<> g(2, 40);
  scanf("%d%d%s%s", &n, &m, s, t);
  for (int i = (0); i <= (n - 1); ++i) s[i] -= t[i];
  sieve(1e6);
  for (int x = (2); x <= (40); ++x) {
    for (int i = (0); i <= (pr[x] - 1); ++i) w[i] = 0;
    for (int i = (0); i <= (n - 1); ++i) w[i % pr[x]] += s[i];
    for (int &y : f[x]) {
      uniform_int_distribution<> gen(2, y - 1);
      int z = gen(rd), zz = 1;
      while (ksm(z, (y - 1) / pr[x], y) == 1) z = gen(rd), ++ccc;
      zz = z = ksm(z, (y - 1) / pr[x], y);
      for (int i = (1); i <= (pr[x]); ++i) {
        int gg = 0, cc = 1;
        for (int j = (0); j <= (pr[x] - 1); ++j)
          gg = (gg + 1ll * cc * (w[j] % y + y)) % y, cc = 1ll * cc * zz % y,
          ++ccc;
        if (gg == 0) return printf("%d %d\n", y, zz), 0;
        zz = 1ll * zz * z % y;
      }
    }
  }
  cerr << " " << ccc << endl;
  return 0;
}
