Задача I. НОД больших чисел

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:2 Мб
Выходной файл:output.txt  

Условие

Юный математик Вася очень любит числа. А еще больше он любит раскладывать их на делители. Однажды ему приснилось достаточно большое q-ичное число, из которого он запомнил только последние n цифр.

Когда он проснулся, ему стало интересно, какие делители могут быть у такого числа. Подумав еще немного, он сформулировал следующую задачу: какой наибольший общий делитель будут иметь все возможные числа, оканчивающиеся заданным набором q-ичных цифр?

Ему сразу же захотелось написать программу, которая бы решала указанную задачу для произвольного набора цифр. Так как Вася не очень хорошо программирует, он обратился за помощью к Вам.

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

В начале входного файла "input.txt" хранятся два натуральных числа q и n, после чего следует ровно n q-ичных разрядов, для которых требуется решить поставленную задачу.
При этом для обозначения цифр, лежащих в диапазоне от 10 до 35, используются строчные символы латинского алфавита.

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

Выходной файл "output.txt" должен содержать искомый делитель, также записанный в q-ичной системе счисления.

Ограничения

2 ≤ q ≤ 36, 0 < n ≤ 4000

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
36 41
10360k898faq2lvf8j4rxhifkd9ilnnobm9il766r
6kzw4bjxrz9chm64eqktymn29
2
2 25
1000000000000000000000000
1000000000000000000000000

0.109s 0.030s 15