Vitya wants to come up with a new game with numbers. This game requires players to convert four-digit non-zero numbers using the following allowed set of actions:
1. You can increase the first digit of a number by 1 if it is not equal to 9.
2. You can decrease the last digit by 1 if it is not equal to 1.
3. You can cycle through all the numbers by one to the right.
4. You can cycle through all the numbers by one to the left.
For example, applying these rules to the number 1234 results in the numbers 2234, 1233, 4123, and 2341, respectively. Victor has not yet come up with the exact rules of the game, but for now he is interested in the question of how to get another from one number in the minimum number of operations.
Input: The input
is given two different four-digit numbers, each of which does not contain zeros. Each number on a new line
Output: The program should output a sequence of four-digit numbers that do not contain zeros. The sequence must start with the first of the given numbers and end with the second of the given numbers, each subsequent number in the sequence must be obtained from the previous number by applying one of the rules. The number of numbers in the sequence should be as small as possible.
Examples
| # |
Input |
Output |
| 1 |
1234
4321 |
1234
2234
3234
4323
4322
4321 |