Credit Card Recovery

Interview

Time limit1sMemory limit128 MB

Summary

Given a 16-digit encrypted string, find all original card numbers that the given encrypt rule (bump min up, max down, swap) would produce, printed in ascending order or banana.

Level: Medium5 of 10
Topics: Brute force, Implementation, String, Simulation
Solved: No attempts yet

Problem

Marko is a member of a frequent flyer club. He collected a lot of award miles and finally decided to treat himself to a trip to Australia. As usually happens, the miles do not cover the whole cost of the trip, so a man from the airline called and asked Marko to email him his credit card number, a string of 16 digits.

Marko knows this is insane, but the man on the other end of the line insists. As a compromise, Marko offered to send the card number encrypted with the following algorithm.

Find the smallest digit in the number. If several digits share the smallest value, take the leftmost one. Call this digit A.
Find the largest digit in the number. If several digits share the largest value, take the rightmost one. Call this digit B.
Increase A by 1, unless A is already 9.
Decrease B by 1, unless B is already 0.
Finally, swap the positions of A and B.

For example, if his card number is 7691002779603269, Marko emails the number 7691802779603261.

Write a program that helps the man from the airline determine Marko's credit card number.

Input

The first and only line contains the number Marko sent in the email, a string of 16 digits from 0 to 9.

The card number can start with the digit 0.

Output

Print every number that can be Marko's credit card number, one per line, sorted in ascending lexicographic order. Do not print the same number twice.

If no valid card number exists, print banana.

Examples3

Example 1
Input
```
7691802779603261
```
Expected output
```
7691002779603269
```
Example 2
Input
```
8381950005575690
```
Expected output
```
banana
```

Example 3

Input

8446462287549826

Expected output

1446462287549896
8446462217549896
8446462287549196