eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Найменше кратне

Найменше кратне

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Задано число X та множину цифр D.

Потрібно дописати до X мінімальну кількість цифр з D, щоб число, що отримали, ділилось на k. При цьому отримане число повинно бути мінімально можливим.

Вхідні дані

Перший рядок вхідного файлу містить два натуральних числа X та k (1X10^1000, 2k100000). У другому рядку записана кількість цифр у множині D. У третьому рядку через пропуск записані ці цифри.

Вихідні дані

Єдиний рядок повинен містити мінімальне число, отримане з X дописуванням цифр з D і кратне k. Якщо такого числа не існує, виведіть -1.

Приклад

Вхідні дані #1
102 101
3
1 0 3
Вихідні дані #1
10201