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;
template <typename T1, typename T2>
string print_iterable(T1 begin_iter, T2 end_iter, int counter) {
  bool done_something = false;
  stringstream res;
  res << "[";
  for (; begin_iter != end_iter and counter; ++begin_iter) {
    done_something = true;
    counter--;
    res << *begin_iter << ", ";
  }
  string str = res.str();
  if (done_something) {
    str.pop_back();
    str.pop_back();
  }
  str += "]";
  return str;
}
vector<int> SortIndex(int size, std::function<bool(int, int)> compare) {
  vector<int> ord(size);
  for (int i = 0; i < size; i++) ord[i] = i;
  sort(ord.begin(), ord.end(), compare);
  return ord;
}
template <typename T>
bool MinPlace(T& a, const T& b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T>
bool MaxPlace(T& a, const T& b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <typename S, typename T>
ostream& operator<<(ostream& out, const pair<S, T>& p) {
  out << "{" << p.first << ", " << p.second << "}";
  return out;
}
template <typename T>
ostream& operator<<(ostream& out, const vector<T>& v) {
  out << "[";
  for (int i = 0; i < (int)v.size(); i++) {
    out << v[i];
    if (i != (int)v.size() - 1) out << ", ";
  }
  out << "]";
  return out;
}
template <class TH>
void _dbg(const char* name, TH val) {
  clog << name << ": " << val << endl;
}
template <class TH, class... TA>
void _dbg(const char* names, TH curr_val, TA... vals) {
  while (*names != ',') clog << *names++;
  clog << ": " << curr_val << ", ";
  _dbg(names + 1, vals...);
}
long long modpow(long long a, long long e, long long p) {
  if (e == 0) return 1;
  if (e % 2 == 0) return modpow(a * a % p, e / 2, p);
  return modpow(a * a % p, e / 2, p) * a % p;
}
const int Z = 1 << 17;
int rev[Z];
long long roots[Z];
void PreRev() {
  assert(Z > 0 and !(Z & (Z - 1)));
  rev[0] = 0;
  for (int i = 1; i < Z; i++)
    rev[i] = (rev[i >> 1] >> 1) ^ ((i & 1) ? (Z >> 1) : 0);
}
void PreRoots(long long p, long long unit_root) {
  for (int k = 1; k < Z; k <<= 1) {
    long long w = modpow(unit_root, Z / (2 * k), p);
    roots[k] = 1;
    for (int i = 1; i < k; i++) {
      roots[k + i] = roots[k + i - 1] * w % p;
    }
  }
}
void FFT(vector<long long>& a, long long p) {
  for (int i = 0; i < Z; i++)
    if (i < rev[i]) swap(a[i], a[rev[i]]);
  for (int k = 1; k < Z; k <<= 1) {
    for (int i = 0; i < Z; i += 2 * k) {
      for (int j = 0; j < k; j++) {
        long long x = a[i + j], y = a[i + k + j] * roots[k + j] % p;
        a[i + j] = x + y;
        a[i + k + j] = x - y;
      }
    }
  }
}
vector<long long> RecursiveFFT(const vector<long long>& seq,
                               long long unit_root, long long p) {
  int N = seq.size();
  if (N == 1) return {seq[0] % p};
  vector<long long> even_seq(N / 2), odd_seq(N / 2);
  for (int i = 0; i < N / 2; i++) {
    even_seq[i] = seq[2 * i];
    odd_seq[i] = seq[2 * i + 1];
  }
  const auto& even_dft = RecursiveFFT(even_seq, unit_root * unit_root % p, p);
  const auto& odd_dft = RecursiveFFT(odd_seq, unit_root * unit_root % p, p);
  vector<long long> dft(N);
  long long current_root = 1;
  for (int i = 0; i < N; i++) {
    dft[i] = (even_dft[i % (N / 2)] + current_root * odd_dft[i % (N / 2)]) % p;
    current_root = current_root * unit_root % p;
  }
  return dft;
}
long long slow_find_root(const vector<long long>& Q, int N, long long p) {
  for (long long z = 2; z <= p - 2; z++) {
    long long res = 0;
    for (int i = N - 1; i >= 0; i--) {
      res = (res * z + Q[i]) % p;
    }
    if (res % p == 0) return z;
  }
  return -1;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N, M;
  cin >> N >> M;
  PreRev();
  vector<long long> pol(Z, 0);
  for (int i = 0; i < N; i++) {
    char c;
    cin >> c;
    pol[i] += c - 'a';
  }
  for (int i = 0; i < N; i++) {
    char c;
    cin >> c;
    pol[i] -= c - 'a';
  }
  for (long long p = Z + 1;; p += Z) {
    bool is_prime = true;
    for (int d = 2; d * d <= p; d++)
      if (p % d == 0) {
        is_prime = false;
        break;
      }
    if (!is_prime) continue;
    long long primitive;
    long long unit_root;
    for (long long a = 2;; a++) {
      if (modpow(a, (p - 1) / 2, p) != 1) {
        primitive = a;
        unit_root = modpow(a, (p - 1) / Z, p);
        break;
      }
    }
    long long pot = 1;
    for (int j = 0; j < (p - 1) / Z; j++) {
      vector<long long> Q = pol;
      long long pot2 = 1;
      for (int i = 0; i < N; i++) Q[i] = Q[i] * pot2 % p, pot2 = pot * pot2 % p;
      PreRoots(p, unit_root);
      FFT(Q, p);
      for (int i = 0; i < Z; i++)
        if (Q[i] % p == 0) {
          if (j == 0 and (i == 0 or i == (Z / 2))) continue;
          long long r = pot * modpow(unit_root, i, p) % p;
          cout << p << " " << r << "\n";
          return 0;
        }
      pot = pot * primitive % p;
    }
  }
}
