Дано число 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 |