Вітя розробляє нову гру з чотирицифровими числами, в яких жодна цифра не може бути нулем. Гравці можуть перетворювати ці числа, виконуючи такі дії:
Збільшити першу цифру на , якщо вона ще не дорівнює .
Зменшити останню цифру на , якщо вона ще не дорівнює .
Зробити циклічний зсув усіх цифр на одну позицію вправо.
Зробити циклічний зсув усіх цифр на одну позицію вліво.
Наприклад, починаючи з числа , можна отримати , , або , застосувавши відповідні дії. Хоча Вітя ще не фіналізував повні правила гри, зараз його цікавить, яка мінімальна кількість операцій необхідна, щоб перетворити одне число в інше.
Вхід містить два різних чотирицифрових числа, кожне з яких не містить нулів.
У відповіді потрібно вивести послідовність чотирицифрових чисел, у жодному з яких немає нулів. Послідовність повинна починатися з першого заданого числа і закінчуватися другим. Кожне наступне число має отримуватися із попереднього однією з дозволених дій. Послідовність має бути якомога коротшою.
Приклад 1