Дистанционный практикум по программированию

Хэширование (англ. hashing) — преобразование по детерминированному алгоритму входного массива данных произвольной длины в выходную битовую строку фиксированной длины. Такие преобразования также называются хэш-функциями или функциями свёртки, а их результаты называют хэшем.

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

В общем случае однозначного соответствия между исходными данными и хэш-кодом нет в силу того, что количество значений хеш-функций меньше, чем вариантов входного массива; существует множество массивов с разным содержимым, но дающих одинаковые хэш-коды —так называемые коллизии. Вероятность возникновения коллизий играет немаловажную роль в оценке качества хеш-функций.

Wikipedia

 

Один из лучших простых способов определить хэш-функцию от строки S длины N следующий:

h(S)= S[0]*P^N-1 +S[1]*P^N-2 + S[2]* P^N-3  +  ...  +  S[N-1]*P⁰

Под S[i] будем понимать ASCII код символа i. Часто для удобства и увеличения скорости вычисления производят в 32 или 64 битном типе с переполнением. Но, к сожалению такой хэш можно взломать независимо от выбираемого p. Ваша задача сделать это.

По заданному p, нужно найти 2 различные непустые строки с одинаковым значением хэш-функции с учетом того, что расчеты ведутся в знаковом 32 битном типе c переполнением.

 

Формат входного файла

 

В первой строке входного файла содержится  1 целое число p (1<=p<=10⁹).

 

Формат выходного файла

 

Выведите 2 строки, имеющие одинаковое значение хэш-функции. Длина каждой строки должна быть не более 100 000 символов. Каждая строка должна содержать только символы от ‘a’ до ‘z’ включительно. Если решений несколько, выведите любое.

 

Пример

Входные данные	Выходные данные
31	abaabaabbbbbabbbbaa abbbbbbaaaabbabaab