CF1184A3.Heidi Learns Hashing (Hard)

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( \sum_{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\leq r \leq p-2$.

The goal is to find $r$ and a prime $p$ ($m \leq p \leq 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.

现在，海蒂准备攻破科瓦里安夫人（Madame Kovarian）的哈希函数。

科瓦里安夫人对姓名变更有着极为严格的规定：仅当对两个姓名应用如下哈希函数时发生哈希碰撞，这两个姓名才可相互替换。然而，该哈希函数是参数化的，因此总能找到一组参数，使得此类碰撞发生。海蒂决定利用这一特性为自己谋利。

给定两个长度均为 $n$ 的字符串 $w_1$、$w_2$，它们均由小写英文字母组成，以及一个整数 $m$。

考虑标准的多项式哈希函数：

$$H_p(w) := \left( \sum_{i=0}^{|w|-1} w_i r^i \right) \bmod(p)$$

其中 $p$ 为某个素数，$r$ 为某个满足 $2\leq r \leq p-2$ 的整数。

目标是找出一个整数 $r$ 和一个素数 $p$（满足 $m \leq p \leq 10^9$），使得 $H_p(w_1) = H_p(w_2)$。

字符串 $w_1$ 和 $w_2$ 是从所有长度为 $n$ 的小写英文字母字符串中独立均匀随机采样得到的。

The first line contains two integers $n$ and $m$ ($10 \le n \le 10^5$, $2 \le m \le 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.

第一行包含两个整数 $n$ 和 $m$（$10 \le n \le 10^5$，$2 \le m \le 10^5$）。

第二行和第三行分别包含单词 $w_1$、$w_2$，它们是独立地、均匀随机地从所有长度为 $n$ 的小写英文字母字符串中采样得到的。

Output integers $p, r$.

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

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

输出整数 $p, r$。

$p$ 应为区间 $[m, 10^9]$ 内的一个素数，且 $r$ 应为满足 $r\in [2,p-2]$ 的整数。

保证至少存在一个解。若存在多个解，输出任意一个即可。

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\geq 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...

在第一个例子中，请注意，尽管 $p=3$ 且 $r=2$ 同样会导致哈希冲突，但这并不是一个正确解，因为 $m$ 为 $5$，所以我们要求 $p\geq 5$。

在第二个例子中，我们已知晓末尾多出了一个字母 'g'。我们只是未意识到 “River Song” 和 “Melody Pond” 的长度不同……