3rdsmallestandlargest-1

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 3^rd Smallest and the 3^rd Largest possible number(numerically). 

Now the number itself might be quite large having up to 10^5 digits and it is also known that the number will have only 1-9 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 3^rd Smallest Number and the 3^rd Largest number separated by a space. If it doesn't exist, instead print "Not possible!"(without the quotes)

Constraints:

1 ≤ T ≤ 10
1 ≤ No \, of \, digits \, in \, N  ≤ 10^5

Scoring:

1 ≤ T ≤ 10, 1 ≤ No \, of \, digits \, in \, N ≤ 10  (20 pts)
1 ≤ T ≤ 10, 10 ≤ No \, of \, digits \, in \, N  ≤ 10^3 (30 pts)
1 ≤ T ≤ 10, 1000 ≤ No \, of \, digits \, in \, N ≤ 10^5 (50 pts)

SAMPLE INPUT
3
123
4
1232

SAMPLE OUTPUT
213 231
Not possible!
1322 3122

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.

Source: hackerearth | Difficulty: EASY


Solutions:
def nex(a,n):
	i=n-2
	while i>=0 and a[i]>=a[i+1] :
		i=i-1
	if i<0 :
		return (False,a)
	j=n-1
	while a[i]>=a[j]:
		j=j-1
	a[i],a[j]=a[j],a[i]
	k=n-1
	j=i+1
	while j<k:
		a[j],a[k]=a[k],a[j]
		j+=1
		k-=1
	return (True,a)
def prev(a,n):
	i=n-2
	while i>=0 and a[i]<=a[i+1] :
		i=i-1
	if i<0 :
		return (False,a)
	j=n-1
	while a[i]<=a[j]:
		j=j-1
	a[i],a[j]=a[j],a[i]
	k=n-1
	j=i+1
	while j<k:
		a[j],a[k]=a[k],a[j]
		j+=1
		k-=1
	return (True,a)
for z in range(int(input())):
	s=input()
	n=len(s)
	a=sorted(s)
	b=a[::-1]
	f=True
	for i in range(2):
		f,a=nex(a,n)
		if not f:
			break
		f,b=prev(b,n)
		if not f:
			break
	if f:
		print(''.join(a),''.join(b))
	else:
		print("Not possible!")


from copy import deepcopy
def next_greater_int(n_list):
	idx = -1
	len_list = len(n_list)
	last_elem = n_list[len_list-1]
	prev_idx = len_list -1
	len_list = len(n_list)
	index = len_list - 2
	while True:
		if index < 0:
			break
		if n_list[index] < n_list[prev_idx]:
			temp = n_list[index]
			n_list[index] = n_list[prev_idx]
			n_list[prev_idx] = temp
			idx = index
			break
		elif n_list[index] == n_list[prev_idx]:
			if index == prev_idx -1:
				index = index -1
				continue
			prev_idx = prev_idx  - 1
			if prev_idx == index:
				index= index -1
			continue
		#else:
		#   prev_idx = index
		index = index - 1
			
	if idx == -1:
		return (False, n_list)
	else:
		a_list = sorted(n_list[idx + 1 :])
		b_list = n_list[:idx+1] + a_list
		return (True, b_list)

def next_smaller_int(n_list):
	idx = -1
	len_list = len(n_list)
	last_elem = n_list[len_list-1]
	prev_idx = len_list -1
	len_list = len(n_list)
	index = len_list - 2
	while True:
		if index < 0:
			break
		if n_list[index] > n_list[prev_idx]:
			temp = n_list[index]
			n_list[index] = n_list[prev_idx]
			n_list[prev_idx] = temp
			idx = index
			break
		elif n_list[index] == n_list[prev_idx]:
			if index == prev_idx -1:
				index = index -1
				continue
			prev_idx = prev_idx  - 1
			if prev_idx == index:
				index= index -1
			else:
				continue
		#else:
		#   prev_idx = index
		index = index-1
			
	if idx == -1:
		(False, n_list)
	else:
		a_list = sorted(n_list[idx + 1 :], reverse=True)
		b_list = n_list[:idx+1] + a_list
		return (True, b_list)

t = int(input())
count = 0
while True:
	if count == t:
		break
	#import pdb
	#pdb.set_trace()
	num = input()
	num1 = sorted(num)
	num2 = deepcopy(num1)
	count += 1
	
	if len(num1) < 3 or len(set(num1)) == 1:
		print("Not possible!")
		continue

	flag, first_greater = next_greater_int(num1)
	if not flag:
		print("Not possible!")
		continue

	flag, second_greater = next_greater_int(first_greater)
	#import pdb
	#pdb.set_trace()
	num2 = sorted(num2, reverse=True)
	flag, first_smaller = next_smaller_int(num2)
	#import pdb
	#pdb.set_trace()
	flag, second_smaller = next_smaller_int(first_smaller)
	print("".join(second_greater), "".join(second_smaller))
		


def next(s):
	l = len(s)
	prev = s[l-1]
	for i in range(l-2,-1,-1):
		if s[i]<prev:
			min = i+1
			for j in range(i+1,l):
				if s[j]>s[i] and s[j]<s[min]:
					min=j
			y = s[:i]+s[min]
			x = s[i+1:min]+s[min+1:]+s[i]
			x = ''.join(sorted(x))
			s= y+x
			break
		prev = s[i]
	return s

def prev(s):
	l = len(s)
	prev = s[l-1]
	for i in range(l-2,-1,-1):
		if s[i]>prev:
			min = i+1
			for j in range(i+1,l):
				if s[j]<s[i] and s[j]>s[min]:
					min=j
			y = s[:i]+s[min]
			x = s[i+1:min]+s[min+1:]+s[i]
			x = ''.join(sorted(x,reverse=True))
			s= y+x
			break
		prev = s[i]
	return s

t = eval(input())
while t:
	s = input()
	l = len(s)
	freq={}
	for i in range(10):
		freq[str(i+1)]=0
	for i in range(l):
		freq[s[i]]+=1
	s=""
	flag=1
	for i in range(10):
		s+=(str(i+1))*freq[str(i+1)]
	for i in range(2):
		s1 = next(s)
		if s1 == s:
			flag=0
			break
		s=s1
	if flag==0:
		print('Not possible!')
	else:
		print(s, end=' ')
		s=""
		for i in range(9,0,-1):
			s+=(str(i))*freq[str(i)]
		for i in range(2):
			s1 = prev(s)
			s=s1
		print(s)
	t-=1