Yet Another String Problem!!

0

0 votes
Problem

Archit loves to challenge people for different tasks but this time Pulkit challenged him with a task.

The task was that given two distinct strings A and B you have to make another string C of the same length as A, by arranging the characters of string A in such a manner it is a lexicographically largest possible string which is strictly smaller than string B.

As Archit is busy playing counter strike, he has asked for your help to win the challenge.

Note: It is not necessary that the length of both the strings A and B is the same. 


INPUT: The first line of input contains a single integer T denoting the number of test cases. Next 2T lines follow each test case contains two lines the first line contains the string A and the second line contains string B.

OUTPUT: For each test case print a single line containing the string C(in lowercase), and if no such string C is possible then print "IMPOSSIBLE"(without quotes).

CONSTRAINTS:

1<=T<=10.

1<=|A|,|B|<=100.

where |X| denotes the length of the Xth String.

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

All possible strings that can be formed by the arrangement of the character of string A, and are strictly less than string B are as follows:

abcd, abdc, acbd, acdb, adcb, adbc, bacd, badc.

Among these the lexicographically largest is badc, which is the answer.

Editor Image

?