Теперь Хайди готова взломать хеш-функцию Мадам Ковариан.
Мадам Ковариан пользуется весьма сложным набором правил для замены имён. Два имени могут быть заменены друг на друга только если следующая хеш-функция на них приводит к коллизии. Однако, хеш-функция параметризована, так что всегда можно подобрать набор параметров, который приводит к коллизии. Хайди решила воспользоваться этим в свою пользу.
Пусть даны строки \(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\), состоящих из строчных латинских букв.
Выходные данные
Выведите целые числа \(p, r\).
\(p\) должно быть простым числом в диапазоне \([m, 10^9]\), а \(r\) должно быть таким целым числом, что \(r\in [2,p-2]\).
Гарантируется, что существует хотя бы одно решение. В случае, если существует несколько решений, выведите любое из них.
Примечание
В первом примере, параметры \(p=3\) и \(r=2\) тоже приводят к коллизии хешей, но они не являются корректным решением, так как \(m\) равно \(5\) и нужно решение с \(p\geq 5\).
Во втором примере мы знаем о дополнительной букве «g» в конце. Просто у строк «River Song» и «Melody Pond» разные длины...
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10 5
bgcbaaaaaa
cccaaaaaaa
|
5 2
|
|
2
|
10 100
melodypond
riversongg
|
118219 79724
|