3rd Smallest and Largest

4.4

7 votes
Easy
Problem

Alice decides to challenge Bob to a problem. She gives him a number.

Bob can rearrange the digits of this number by applying pair-wise swaps between any 2 digits in the number as many times as he wants. Now Alice asks him to write down all the distinct numbers that he can form and sort them. Of these she wants him to tell her the 3rd Smallest and the 3rd Largest possible number(numerically).

Now the number itself might be quite large having up to 105 digits and it is also known that the number will have only 19 as digits(Alice does not like 0 for some reason).
Help Bob with this task!

Input:

First line contains T which is the number of test cases.
T lines follow each containing an integer N .

Output:

For each input N, output one line containing the 3rd Smallest Number and the 3rd Largest number separated by a space. If it doesn't exist, instead print "Not possible!"(without the quotes)

Constraints:

  • 1T10
  • 1NoofdigitsinN105

Scoring:

  • 1T10,1NoofdigitsinN10 (20 pts)
  • 1T10,10NoofdigitsinN103 (30 pts)
  • 1T10,1000NoofdigitsinN105 (50 pts)
Sample Input
3
123
4
1232
Sample Output
213 231
Not possible!
1322 3122
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

Case 1: We can make these numbers from 123 123,132,213,231,312,321. Of these the 3rd from the front is 213 and from back is 231.

Case 2: We can only make 4 from this. Hence it is not possible!

Case 3: We can make 12 distinct numbers from this number. The smallest 3 are 1223,1232,1322. The largest 3 are 3221,3212,3122.

Contributers:
Editor Image

?