A3. Хайди изучает хеширование (сложная)
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Теперь Хайди готова взломать хеш-функцию Мадам Ковариан.

Мадам Ковариан пользуется весьма сложным набором правил для замены имён. Два имени могут быть заменены друг на друга только если следующая хеш-функция на них приводит к коллизии. Однако, хеш-функция параметризована, так что всегда можно подобрать набор параметров, который приводит к коллизии. Хайди решила воспользоваться этим в свою пользу.

Пусть даны строки $$$w_1$$$ и $$$w_2$$$ одинаковой длины $$$n$$$, состоящей из строчных латинских букв, и целое число $$$m$$$.

Рассмотрим стандартный полиномиальный хеш:

$$$H_p(w) := \left( \sum_{i=0}^{|w|-1} w_i r^i \right) \mbox{mod}(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$$$, состоящих из строчных латинских букв.

Входные данные

Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$10 \le n \le 10^5$$$, $$$2 \le m \le 10^5$$$).

Вторая и третья строки содержат строки $$$w_1$$$ и $$$w_2$$$, которые были выбраны случайно и независимо друг от друга из всех слов длины $$$n$$$, состоящих из строчных латинских букв.

Выходные данные

Выведите целые числа $$$p, r$$$.

$$$p$$$ должно быть простым числом в диапазоне $$$[m, 10^9]$$$, а $$$r$$$ должно быть таким целым числом, что $$$r\in [2,p-2]$$$.

Гарантируется, что существует хотя бы одно решение. В случае, если существует несколько решений, выведите любое из них.

Примеры
Входные данные
10 5
bgcbaaaaaa
cccaaaaaaa
Выходные данные
5 2
Входные данные
10 100
melodypond
riversongg
Выходные данные
118219 79724
Примечание

В первом примере, параметры $$$p=3$$$ и $$$r=2$$$ тоже приводят к коллизии хешей, но они не являются корректным решением, так как $$$m$$$ равно $$$5$$$ и нужно решение с $$$p\geq 5$$$.

Во втором примере мы знаем о дополнительной букве «g» в конце. Просто у строк «River Song» и «Melody Pond» разные длины...