Numbers

Vitya is designing a new game involving four-digit numbers, where none of the digits can be zero. Players can transform these numbers using the following actions:

1. Increase the first digit by 1, provided it is not already 9.

2. Decrease the last digit by 1, provided it is not already 1.

3. Perform a cyclic shift of all digits one position to the right.

4. Perform a cyclic shift of all digits one position to the left.

For instance, starting with the number 1234, you can transform it into 2234, 1233, 4123, or 2341 by applying the respective actions. Although Vitya hasn't finalized the complete rules of the game, he is currently interested in determining the minimum number of operations required to transform one number into another.

Input

The input consists of two distinct four-digit numbers, each without any zeros.

Output

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

Examples