E. Большое число и остаток
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Степана есть большое целое положительное число.

Рассмотрим все циклические сдвиги числа, если рассматривать его как строку, которые также являются числами (то есть не начинаются с нуля). Будем называть такие циклические сдвиги хорошими. Например, для числа 10203 хорошими циклическими сдвигами являются само число 10203, а также числа 20310 и 31020.

Степану стало интересно, какой наименьший остаток от деления на заданное число m можно получить, поделив на m все хорошие циклические сдвиги заданного числа.

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

В первой строке следует число, которое есть у Степана. Количество цифр в нём от 2 до 200 000. Гарантируется, что это число не начинается с нуля.

Во второй строке следует целое число m (2 ≤ m ≤ 108) — число, на которое Степан будет делить хорошие циклические сдвиги.

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

Выведите искомый наименьший остаток от деления на число m всех хороших циклических сдвигов заданного числа.

Примеры
Входные данные
521
3
Выходные данные
2
Входные данные
1001
5
Выходные данные
0
Входные данные
5678901234567890123456789
10000
Выходные данные
123
Примечание

В первом примере все хорошие циклические сдвиги числа 521 (они равны 521, 215, 152) дают одинаковый остаток 2 при делении на 3.

Во втором примере для заданного числа есть только два хороших циклических сдвига: на ноль позиций и на одну позицию вправо. Сдвиг на ноль позиций равен 1001 и остаток от деления на 5 равен 1, а сдвиг на одну позицию вправо равен 1100 и остаток от деления на 5 равен 0, который является минимальным возможным остатком.