A12738. 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) \bmod 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.

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.

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.

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