Большое число

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

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

В первой строке содержится набор допустимых цифр S в порядке возрастания без пробелов и без повторений. Набор цифр может быть пуст. Во второй строке содержится число K (1 <= K <= 10^5).

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

Выведите одно искомое число. Если искомого числа не существует, выведите –1.

Примеры