Олимпиадный тренинг

Задача . Наименьшее кратное


Задача

Темы: Обход в ширину

Дано число X и множество цифр D. Требуется дописать к X минимальное количество цифр из D, чтобы получившееся число делилось на k. При этом получившееся число должно быть минимально возможным.


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

Первая строка входного файла содержит два натуральных числа X и k (1 ≤ X ≤ 101000, 2 ≤ k ≤ 105). Во второй строке записано количество цифр во множестве D. В третьей строке через пробел записаны эти цифры (если множество D пусто, то третьей строки во входных данных нет, что важно при считывании данных по строкам).


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

Единственная строка должна содержать минимальное число, полученное из X дописыванием цифр из D и кратное k. Если такого числа не существует, выведите -1.

Примеры

входные данные выходные данные
102 101
3
1 0 3
10201
202 101
3
1 0 3
202

time 500 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w641
Комментарий учителя