Задача Remake. Розглянемо 7-значні цілі числа в десятковій системі числення, дозволяючи нулі в старших розрядах. Тобто, числа від 0000000 до 9999999. Над числом дозволено виконувати такі перетворення:
- додати 1 (не застосовне до 9999999);
- відняти 1 (не застосовне до 0000000);
- домножити на будь-яке натуральне число k від 2 до 9(застосовне тільки коли отриманий добуток не перевищує 9999999);
- поділити на будь-яке натуральне число k від 2 до 9(застосовне тільки коли число до перетворення кратне k);
- виконати циклічний зсув вліво, тобто стерти найстаршу цифру і дописати її справа (наприклад,1234567 → 2345671; застосовне до будь-якого числа);
- виконати циклічний зсув вправо, тобто стерти наймолодшу цифру і дописати її зліва (наприклад,1234567 → 7123456; застосовне до будь-якого числа).
Напишіть програму, яка за двома вказаними 7-значними числами A та B знаходитиме, як перетворити перше у друге за мінімальну кількість кроків.
Технічні умови. Програма Remake читає з клавіатури (пристрою стандартного введення) початкове та кінцеве значення A та B. Кожне значення складається рівно з 7-ми десяткових цифр, між значеннями знаходиться рівно один пропуск.
Програма виводить на пристрій стандартного виведення (екран) спочатку мінімальну кількість перетворень M, далі треба вивести M+1 штук 7-цифрових чисел, де перше дорівнює A, останнє дорівнює B, і кожне наступне отримане з попереднього згідно одного з перетворень. Числа, менші106, мають бути доповнені нулями до 7-значних. Якщо можливі різні правильні послідовності з однаковою мінімальною кількістю перетворень — виводьте будь-яку одну з них. Числа виводяться через пропуск.
Приклади
Введення
3330333 3333033
Виведення
1 3330333 3333033
Введення
0000000 0370370
Виведення
6 0000000 0000001 1000000 0999999 0111111 0037037 0370370