Numbers#4007

Numbers

1 second

128 megabytes

Very easy

Vitya is designing a new game involving four-digit numbers that do not contain zeros. Players can transform these numbers using the following actions:

Increase the first digit by $1$ , provided it is not $9$ .
Decrease the last digit by $1$ , provided it is not $1$ .
Rotate all digits one position to the right.
Rotate all digits one position to the left.

For instance, applying these actions to the number $1234$ could result in $2234$ , $1233$ , $4123$ , or $2341$ . Although Vitya hasn't finalized the game's rules, he is curious about how to transform one number into another using the fewest possible operations.

Input

You will be given two distinct four-digit numbers, each without zeros.

Output

Provide a sequence of four-digit numbers, none containing zeros. The sequence should begin with the first number and end with the second, with each number in the sequence derived from the previous one by applying one of the allowed actions. The sequence should be as short as possible.

Examples

Example 1

Loading