eolymp
Problems

Числа

Числа

Time limit 1 second
Memory limit 128 MiB

   Витя хочет придумать новую игру с числами. В этой игре от игроков требуется преобразовать четырёхзначные числа, не содержащие нулей, при помощи следующего разрешённого набора действий:

  1. Можно увеличить первую цифру числа на 1, если она не равна 9.

  2. Можно уменьшить последнюю цифру на 1, если она не равна 1.

  3. Можно циклически сдвинуть все цифры на одну вправо.

  4. Можно циклически сдвинуть все цифры на одну влево. 

   Например, применяя эти правила к числу 1234 можно получить числа 2234, 1233, 4123 и 2341 соответственно. Точные правила игры Витя пока не придумал, но пока его интересует вопрос, как получить из одного числа другое за минимальное количество операций.

Input data

   Два различных четырёхзначных числа, каждое из которых не содержит нулей.

Output data

   Вывести последовательность четырёхзначных чисел, не содержащих нулей. Последовательность должна начинаться первым из заданных чисел и заканчиваться вторым из данных чисел, каждое последующее число в последовательности должно быть получено из предыдущего числа применением одного из правил. Количество чисел в последовательности должно быть минимально возможным.

Examples

Input example #1
1234
4321
Output example #1
1234
2234
3234
4323
4322
4321