Question name:Smallest KMP
Chef has a string SS. He also has another string PP, called pattern. He wants to find the pattern in SS, but that might be impossible. Therefore, he is willing to reorder the characters of SS in such a way that PP occurs in the resulting string (an anagram of SS) as a substring.
Since this problem was too hard for Chef, he decided to ask you, his genius friend, for help. Can you find the lexicographically smallest anagram of SS that contains PP as substring?
Note: A string BB is a substring of a string AA if BB can be obtained from AA by deleting several (possibly none or all) characters from the beginning and several (possibly none or all) characters from the end.
Input
- The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
- The first line of each test case contains a single string SS.
- The second line contains a single string PP.
Output
For each test case, print a single line containing one string ― the smallest anagram of SS that contains PP.
Constraints
- 1 \le T \le 101≤T≤10
- 1 \le |P| \le |S| \le 10^51≤∣P∣≤∣S∣≤105
- SS and PP contain only lowercase English letters
- there is at least one anagram of SS that contains PP
Subtasks
Subtask #1 (20 points): |S| \le 1,000∣S∣≤1,000
Subtask #2 (80 points): |S| \le 10^5∣S∣≤105
Sample 1:
Input
Output
3 akramkeeanany aka supahotboy bohoty daehabshatorawy badawy
aaakaeekmnnry abohotypsu aabadawyehhorst