Волнистым числом называется такое целое положительное число, что для каждой цифры десятичного представления, не являющейся первой или последней, она либо строго больше обеих соседних с ней цифр, либо строго меньше обеих соседних с ней цифр. Например, числа 35270, 102, 747, 20 и 3 являются волнистыми, а числа 123, 1000 и 2212 — нет.
Для двух заданных целых чисел n и k требуется найти k-е по величине волнистое число r, которое делится нацело на n.
Ваша задача — написать программу для нахождения искомого числа r в случае, если оно не превосходит 1014.
Выходные данные
Требуется вывести единственное целое число r — ответ на задачу. Если такого числа не существует или оно больше 1014, то требуется вывести «-1» (минус единицу без кавычек).
Примечание
Значения первых четырех волнистых чисел кратных n для первого примера входных данных: 492, 615, 738 и 1845.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
123 4
|
1845
|
|
2
|
100 1
|
-1
|
|
3
|
97461 457
|
1805270103
|