407327: GYM102766 A Singhal and Swap

If you want to practice topicwise questions in the ladder way like a2oj , do register on my site http://codedigger.tech after the contest. Here you will get Handpicked Topicwise Questions from codeforces, codechef, uva and spoj for your better practice. Best of Luck.

Singhal has two strings $$$S$$$ and $$$T$$$ consisting of lowercase English Letters.

He wants to obtain string $$$S$$$ lexicographically smallest possible. He can do the following operation any number of times: choose an index $$$pos_1$$$ in the string $$$S$$$, choose an index $$$pos_2$$$ in the string $$$T$$$, and swap $$$s_{pos_1}$$$ with $$$t_{pos_2}$$$.

String $$$p$$$ is lexicographically smaller than string $$$q$$$,

• if $$$p$$$ is a prefix of $$$q$$$, $$$p \neq q$$$
• in the first position where $$$p$$$ and $$$q$$$ differ, the string $$$p$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$q$$$.

For example, abc is lexicographically smaller than abcd , abd is lexicographically smaller than abec , afa is not lexicographically smaller than ab and a is not lexicographically smaller than a.

Note: You have not to minimize number of operations and any index of both string can be chosen more than once.

The first line contains a single integer $$$t (1 \le t \le 100)$$$ — the number of test cases in the input. Then $$$t$$$ test cases follow.

Each query contains two lines. The first line contains a string $$$S (1 \le |S| \le 100)$$$ , and the second line contains a string $$$T(1 \le |T| \le 100)$$$. $$$|S|$$$ and $$$ |T|$$$ is the length of the string $$$S$$$ and $$$T$$$ respectively.

Note: Both strings will have only lowercase English Letters.

For each test from the input print lexicographical smallest possible string $$$S$$$. Print the answers to the tests in the order in which the tests are given in the input.

5
ab
a
abc
abc
abd
codedigger
dbc
a
adb
codealittle

aa
aab
abc
abc
aab

In the first query — swap($$$s_2,t_1$$$) to get smallest lexicographical possible.

In the second query — swap($$$s_2,t_1$$$) to get $$$S$$$ = aac and $$$T$$$ = bbc, then swap($$$s_3,t_1$$$)to get $$$S$$$ = aab.