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>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx")
using namespace std;
using Int = long long;
template <class T1, class T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &a) {
  return os << "(" << a.first << ", " << a.second << ")";
};
template <class T>
void pv(T a, T b) {
  for (T i = a; i != b; ++i) cerr << *i << " ";
  cerr << endl;
}
template <class T>
void chmin(T &t, const T &f) {
  if (t > f) t = f;
}
template <class T>
void chmax(T &t, const T &f) {
  if (t < f) t = f;
}
unsigned xrand() {
  static unsigned x = 314159265, y = 358979323, z = 846264338, w = 327950288;
  unsigned t = x ^ x << 11;
  x = y;
  y = z;
  z = w;
  return w = w ^ w >> 19 ^ t ^ t >> 8;
}
Int power(Int a, Int e, Int m) {
  Int x = a % m, y = 1 % m;
  for (; e; e >>= 1) {
    if (e & 1) {
      y = (y * x) % m;
    }
    x = (x * x) % m;
  }
  return y;
}
constexpr int LIM = 1000000;
constexpr int MM = 100000;
bool isnp[LIM];
int primesLen;
Int primes[LIM];
int N, M;
char A[100010], B[100010];
Int c[100010];
int main() {
  for (int p = 2; p < LIM; ++p) {
    if (!isnp[p]) {
      for (int n = 2 * p; n < LIM; n += p) {
        isnp[n] = true;
      }
    }
  }
  for (int p = MM; p < LIM; ++p) {
    if (!isnp[p]) {
      primes[primesLen++] = p;
    }
  }
  cerr << "|primes| = " << primesLen << endl;
  for (; ~scanf("%d%d", &N, &M);) {
    scanf("%s%s", A, B);
    for (;;) {
      for (int k = 3; k < 100; ++k) {
        fill(c, c + k, 0);
        for (int pos = 0; pos < N; ++pos) {
          c[pos % k] += (B[pos] - A[pos]);
        }
        for (int i = 0; i < primesLen; ++i) {
          const Int p = primes[i];
          if ((p - 1) % k == 0) {
            for (int iter = 0; iter < 3; ++iter) {
              const Int b = 2 + xrand() % (p - 3);
              const Int r = power(b, (p - 1) / k, p);
              if (2 <= r && r <= p - 2) {
                Int s = 0;
                for (int j = k; j--;) {
                  s = (s * r + c[j]) % p;
                }
                if (s == 0) {
                  cerr << "found k = " << k << endl;
                  printf("%lld %lld\n", p, r);
                  goto found;
                }
              }
            }
          }
        }
      }
    }
  found : {}
  }
  return 0;
}
