Даны цифры и длина числа N. Выведите все числа длины N, составленные из данных цифр, в которых никакие две соседние цифры не совпадают.
Формат входных данных
Первая строка: цифры через пробел (от 2 до 5 цифр)
Вторая строка: длина числа N (2 ≤ N ≤ 5)
Формат выходных данных
Все подходящие числа, каждое на отдельной строке. Числа выводить в лексикографическом порядке.
ОБЪЯСНЕНИЕ:
Числа 11, 22, 33 не подходят, так как соседние цифры одинаковые.
ПОДСКАЗКА:
Перед добавлением цифры проверяй, не равна ли она последней добавленной. Если равна — это отсечение, пропускаем эту ветку.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 2
3
|
121
212
|