As a member of a frequent flyer club, Marko has collected many reward miles and finally decided to treat himself to a trip to Australia. However, as is usually the case, the reward miles do not cover all the travel expenses, so a gentleman from the airline called him and asked him to send his credit card number (a sequence of 16 digits) via email.

Marko is aware that this is insane, but the gentleman on the other end of the phone line insists on it. As a compromise, Marko offered to send the card number encrypted with the following algorithm:

• Marko will find the smallest digit in the number, and if there are multiple, he will choose the first one from the left. Let's call this digit $A$.
• Then he will find the largest digit in the number, and if there are multiple, he will choose the last one from the right. Let's call this digit $B$.
• He will increment digit $A$ by 1, unless it is already equal to 9.
• He will decrement digit $B$ by 1, unless it is already equal to 0.
• Finally, Marko will swap the positions of digits $A$ and $B$.

For example, if his card number is 7691 0027 7960 3269, then Marko will send the following number in the email: 7691 8027 7960 3261.

Write a program that will help the gentleman from the airline determine Marko's credit card number.

Input

The first and only line contains a sequence of 16 digits '0' - '9', the number that Marko sent in the email.

Note: The credit card number can start with the digit '0'.

Output

Print all possible numbers for Marko's credit card, one per line.

If there is no valid credit card number, print "banana".

Examples

Input 1

7691802779603261

Output 1

7691002779603269

Input 2

8381950005575690

Output 2

banana

Input 3

8446462287549826

Output 3

1446462287549896
8446462217549896
8446462287549196