Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Chef has a string $S$. He also has another string $P$, called *pattern*. He wants to find the pattern in $S$, but that might be impossible. Therefore, he is willing to reorder the characters of $S$ in such a way that $P$ occurs in the resulting string (an anagram of $S$) 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 $S$ that contains $P$ as substring?

Note: A string $B$ is a substring of a string $A$ if $B$ can be obtained from $A$ 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 $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single string $S$.
The second line contains a single string $P$.

------  Output ------
For each test case, print a single line containing one string ― the smallest anagram of $S$ that contains $P$.

------  Constraints ------
$1 ≤ T ≤ 10$
$1 ≤ |P| ≤ |S| ≤ 10^{5}$
$S$ and $P$ contain only lowercase English letters
there is at least one anagram of $S$ that contains $P$

------  Subtasks ------
Subtask #1 (20 points): $|S| ≤ 1,000$

Subtask #2 (80 points): $|S| ≤ 10^{5}$

----- Sample Input 1 ------ 
3

akramkeeanany

aka

supahotboy

bohoty

daehabshatorawy

badawy
----- Sample Output 1 ------ 
aaakaeekmnnry

abohotypsu

aabadawyehhorst

Difficulty: MEDIUM
Tags: String algorithms

Data structures
Skill types: Data structures

Starter code:

Solutions:
for _ in range(int(input())):
	a = input()
	b = input()
	a_small = ''
	a_big = ''
	a_small1 = ''
	a_big1 = ''
	a = list(a)
	b = list(b)
	for i in range(len(b)):
		a.remove(b[i])
	a = ''.join(a)
	b = ''.join(b)
	for i in range(len(a)):
		if ord(a[i]) <= ord(b[0]):
			a_small += a[i]
		elif a[i]:
			a_big += a[i]
	ans = ''.join(sorted(a_small)) + b + ''.join(sorted(a_big))
	for i in range(len(a)):
		if ord(a[i]) < ord(b[0]):
			a_small1 += a[i]
		elif a[i]:
			a_big1 += a[i]
	ans1 = ''.join(sorted(a_small1)) + b + ''.join(sorted(a_big1))
	print(min(ans, ans1))


for _ in range(int(input())):
	s = list(str(input()))
	p = list(str(input()))
	s_26 = [0] * 26
	p_26 = [0] * 26
	to_add = [0] * 26
	for i in s:
		s_26[ord(i) - 97] += 1
	for i in p:
		p_26[ord(i) - 97] += 1
	for i in range(26):
		to_add[i] = s_26[i] - p_26[i]
	ans = []
	for i in range(26):
		if i <= ord(p[0]) - 97:
			ans.append(chr(i + 97) * to_add[i])
	ans += p
	for i in range(26):
		if i > ord(p[0]) - 97:
			ans.append(chr(i + 97) * to_add[i])
	ans = ''.join((i for i in ans))
	ans1 = []
	for i in range(26):
		if i < ord(p[0]) - 97:
			ans1.append(chr(i + 97) * to_add[i])
	ans1 += p
	for i in range(26):
		if i >= ord(p[0]) - 97:
			ans1.append(chr(i + 97) * to_add[i])
	ans1 = ''.join((i for i in ans1))
	print(min(ans, ans1))


for _ in range(int(input())):
	s = input()
	p = input()
	pli = list(p)
	sli = list(s)
	front = []
	middle = ''
	end = []
	for a in p:
		if a in sli:
			sli.remove(a)
	for i in range(len(sli)):
		if sli[i] < pli[0]:
			front.append(sli[i])
		elif sli[i] == pli[0]:
			middle += sli[i]
		else:
			end.append(sli[i])
	front.sort()
	end.sort()
	front = ''.join(map(str, front))
	end = ''.join(map(str, end))
	print(min(front + p + middle + end, front + middle + p + end))


for _ in range(int(input())):
	s = input()
	p = input()
	u = [p[0]]
	for e in p[1:]:
		if e not in u:
			u.append(e)
	s = s + p[0]
	s = ''.join(sorted(s))
	for e in p:
		s = s.replace(e, '', 1)
	pos = 0
	if u[0] < u[1]:
		pos = s.rfind(p[0])
	else:
		pos = s.find(p[0])
	print(s[:pos] + p + s[pos + 1:])


for _ in range(int(input())):
	s = input()
	p = input()
	freq = [p[0]]
	for i in p[1:]:
		if i not in freq:
			freq.append(i)
			break
	s += p[0]
	s = ''.join(sorted(s))
	for j in p:
		s = s.replace(j, '', 1)
	cnt = 0
	if freq[0] < freq[1]:
		cnt = s.rfind(p[0])
	else:
		cnt = s.find(p[0])
	print(s[:cnt] + p + s[cnt + 1:])


tests = int(input())
for i in range(tests):
	s = input()
	p = input()
	arr = [0] * 26
	for j in s:
		arr[ord(j) - 97] += 1
	for j in p:
		arr[ord(j) - 97] -= 1
	ans = ''
	p_added = False
	for j in range(26):
		add = chr(97 + j) * arr[j]
		if add + p > p + add and (not p_added):
			ans += p
			p_added = True
		ans += add
	if not p_added:
		ans += p
	print(ans)


import os, sys, io, math
from array import array
from math import *
from collections import Counter
I = lambda : [*map(int, sys.stdin.readline().split())]
IS = lambda : input()
IN = lambda : int(input())
IF = lambda : float(input())
for _ in range(IN()):
	(s, k) = (IS(), IS())
	c = Counter(s)
	for i in k:
		c[i] -= 1
	(a, b) = ('', '')
	for i in 'abcdefghijklmnopqrstuvwxyz':
		if i == k[0]:
			b += k
		a += i * c[i]
		b += i * c[i]
		if i == k[0]:
			a += k
	print(a if a < b else b)


from collections import Counter
t = int(input())
for ti in range(t):
	st = input()
	p = input()
	c = Counter(st)
	for i in p:
		c[i] -= 1
	a = ''
	x = ''
	for i in 'abcdefghijklmnopqrstuvwxyz':
		if i == p[0]:
			x += p
		a += i * c[i]
		x += i * c[i]
		if i == p[0]:
			a += p
	print(a if a < x else x)


from collections import Counter
T = int(input())
for x in range(T):
	S = str(input())
	P = str(input())
	A = [P[0]]
	p = Counter(P)
	for y in P[1:]:
		if y not in A:
			A.append(y)
			break
	S = list(S)
	i = 0
	while i < len(S):
		if p[S[i]] > 0:
			p[S[i]] -= 1
			del S[i]
		else:
			i += 1
	S.append(P[0])
	S = ''.join(sorted(S))
	b = 0
	if A[0] < A[1]:
		b = S.rfind(P[0])
	else:
		b = S.find(P[0])
	print(S[:b] + P + S[b + 1:])


t = int(input())
for i in range(t):
	s = input()
	p = input()
	u = [p[0]]
	for j in p[1:]:
		if j not in u:
			u.append(j)
			break
	s += p[0]
	s = ''.join(sorted(s))
	for k in p:
		s = s.replace(k, '', 1)
	c = 0
	if u[0] < u[1]:
		c = s.rfind(p[0])
	else:
		c = s.find(p[0])
	print(s[:c] + p + s[c + 1:])


from collections import Counter
t = int(input())
for i in range(t):
	s = input()
	p = input()
	u = [p[0]]
	need = Counter(p)
	for j in p[1:]:
		if j not in u:
			u.append(j)
			break
	s = list(s)
	i = 0
	while i < len(s):
		if need[s[i]] > 0:
			need[s[i]] -= 1
			del s[i]
		else:
			i += 1
	s.append(p[0])
	s = ''.join(sorted(s))
	c = 0
	if u[0] < u[1]:
		c = s.rfind(p[0])
	else:
		c = s.find(p[0])
	print(s[:c] + p + s[c + 1:])


for _ in range(int(input())):
	s = str(input())
	p = str(input())
	if len(s) == len(p):
		print(p)
	else:
		res = ''
		flag = 1
		for i in range(1, len(p)):
			if ord(p[i]) == ord(p[i - 1]):
				continue
			if ord(p[i]) < ord(p[i - 1]):
				flag = 0
			break
		ordP1 = ord(p[0]) - ord('a') + flag
		scount = [0] * 26
		for c in s:
			scount[ord(c) - ord('a')] += 1
		for c in p:
			scount[ord(c) - ord('a')] -= 1
		for i in range(ordP1):
			while scount[i] > 0:
				res += chr(i + ord('a'))
				scount[i] -= 1
		res += p
		for i in range(ordP1, 26):
			while scount[i] > 0:
				res += chr(i + ord('a'))
				scount[i] -= 1
		print(res)


for _ in range(int(input())):
	s = input()
	p = input()
	u = []
	u.append(p[0])
	for i in p[1:]:
		if i not in u:
			u.append(i)
	s += p[0]
	s = ''.join(sorted(s))
	for i in p:
		s = s.replace(i, '', 1)
	x = 0
	if u[0] < u[1]:
		x = s.rfind(p[0])
	else:
		x = s.find(p[0])
	print(s[:x] + p + s[x + 1:])


for _ in range(int(input())):
	s1 = input()
	s2 = input()
	l = [0] * 26
	for i in s1:
		l[ord(i) - ord('a')] += 1
	for i in s2:
		l[ord(i) - ord('a')] -= 1
	(k, s, s1) = (ord(s2[0]) - ord('a'), '', '')
	for i in range(26):
		if i == k:
			s += chr(ord('a') + i) * l[i]
			s += s2
			s1 += s2
			s1 += chr(ord('a') + i) * l[i]
		else:
			s += chr(ord('a') + i) * l[i]
			s1 += chr(ord('a') + i) * l[i]
	print(min(s, s1))


import math
for i in range(int(input())):
	s = list(input())
	p = list(input())
	for v in p:
		s.remove(v)
	deb = []
	fin = []
	mid = []
	for (i, v) in enumerate(s):
		if p[0] > v:
			deb.append(v)
		elif p[0] == v:
			mid.append(v)
		else:
			fin.append(v)
	deb = sorted(deb)
	fin = sorted(fin)
	print(min(''.join(deb + mid + p + fin), ''.join(deb + p + mid + fin)))


for _ in range(int(input())):
	s = input()
	p = input()
	list1 = []
	list1[:0] = s
	list2 = []
	list2[:0] = p
	for i in list2:
		list1.remove(i)
	list1.sort()
	str1 = ''
	str2 = ''
	s = str1.join(list1)
	p = str2.join(list2)
	temp = p[0]
	empty = ''
	third = ''
	second = ''
	for i in range(len(s)):
		if s[i] < temp:
			empty = empty + s[i]
		elif s[i] == temp:
			third = third + s[i]
		else:
			second = second + s[i]
	print(min(empty + third + p + second, empty + p + third + second))


for _ in range(int(input())):
	s = input()
	p = input()
	i = 0
	d = {}
	for l in s:
		if l in d:
			d[l] = d[l] + 1
		else:
			d[l] = 1
	for k in p:
		d[k] = d[k] - 1
	res = ''
	res1 = ''
	t = p[0]
	d = {k: v for (k, v) in sorted(d.items(), key=lambda item: item[0])}
	for (k, v) in d.items():
		if k == t:
			res1 += p
			res1 += k * v
			res += k * v
			res += p
		else:
			res += k * v
			res1 += k * v
	print(min(res, res1))


try:
	for _ in range(int(input())):
		n = input()
		t = input()
		a = [0 for i in range(26)]
		for i in n:
			a[ord(i) - 97] += 1
		for i in t:
			a[ord(i) - 97] -= 1
		last = ord(t[0]) - 97
		s1 = ''
		s2 = ''
		for i in range(26):
			if last == i:
				s1 += chr(97 + i) * a[i]
				s1 += t
				s2 += t
				s2 += chr(97 + i) * a[i]
			else:
				s1 += chr(97 + i) * a[i]
				s2 += chr(97 + i) * a[i]
		print(min(s1, s2))
except Exception:
	pass


testcase = int(input())
for _ in range(testcase):
	string = input()
	pattern = input()
	result = ''
	cnt = [0] * 26
	for c in string:
		cnt[ord(c) - ord('a')] += 1
	for c in pattern:
		cnt[ord(c) - ord('a')] -= 1
	flag = 1
	for i in range(1, len(pattern)):
		if pattern[i] == pattern[i - 1]:
			continue
		if pattern[i] < pattern[i - 1]:
			flag = 0
		break
	index = ord(pattern[0]) - ord('a') + flag
	for i in range(0, index):
		while cnt[i] > 0:
			result += chr(i + ord('a'))
			cnt[i] -= 1
	result += pattern
	for i in range(index, 26):
		while cnt[i] > 0:
			result += chr(i + ord('a'))
			cnt[i] -= 1
	print(result)


import collections

def solve(s, p):
	cnter = collections.Counter(s)
	alph = 'abcdefghijklmnopqrstuvwxyz'
	for cp in p:
		cnter[cp] -= 1
	lex = ''
	lex_alt = ''
	for c in alph:
		if c not in cnter:
			continue
		if c == p[0]:
			lex += cnter[c] * c
			lex += p
			lex_alt += p
			lex_alt += cnter[c] * c
		else:
			lex += cnter[c] * c
			lex_alt += cnter[c] * c
	print(min(lex, lex_alt))
n = int(input())
for _ in range(n):
	solve(input(), input())


t = int(input())
for tc in range(t):
	s = input()
	p = input()
	d = {}
	for i in range(len(s)):
		try:
			d[s[i]] += 1
		except:
			d[s[i]] = 1
	for i in range(len(p)):
		d[p[i]] -= 1
	d = {k: v for (k, v) in sorted(d.items(), key=lambda item: item[0])}
	res = ''
	res1 = ''
	trigger = p[0]
	for (k, v) in d.items():
		if k == trigger:
			res1 += p
			res1 += k * v
			res += k * v
			res += p
		else:
			res += k * v
			res1 += k * v
	print(min(res, res1))


from collections import defaultdict as d

def solve():
	string1 = input()
	string2 = input()
	ans = string2
	mp = d(int)
	for i in string1:
		mp[i] += 1
	for i in ans:
		mp[i] -= 1
		if mp[i] == 0:
			del mp[i]
	f = ans[0]
	front = ''
	end = ''
	same = ''
	for i in sorted(mp.keys()):
		run = mp[i]
		if i < f:
			front += i * run
		elif i == f:
			same += i * run
		else:
			end += i * run
	return min(front + same + ans + end, front + ans + same + end)
t = int(input())
while t != 0:
	res = solve()
	print(res)
	t -= 1


for _ in range(int(input())):
	n1 = list((char for char in input()))
	a = input()
	f = []
	m = ''
	l = []
	n2 = list((char for char in a))
	for i in a:
		n1.remove(i)
	for i in range(len(n1)):
		if n1[i] < a[0]:
			f.append(n1[i])
		elif n1[i] == a[0]:
			m += n1[i]
		else:
			l.append(n1[i])
	f = ''.join(sorted(f))
	l = ''.join(sorted(l))
	print(min(f + m + a + l, f + a + m + l))


from collections import Counter
t = int(input())
while t > 0:
	s = input()
	x = []
	y = []
	p = input()
	k = list(s)
	l = list(p)
	u = p[0]
	i = 0
	z = Counter(l)
	nu = Counter(l)
	z.pop(u)
	e = list(z)
	q = Counter(k)
	r = []
	if len(s) == len(p):
		print(p)
	else:
		for o in nu:
			q[o] -= nu[o]
		for o in q:
			r.extend([o] * q[o])
		n = len(r)
		while i < n:
			if r[i] < u:
				x.append(r[i])
			elif r[i] == u:
				if r[i] <= e[0]:
					x.append(r[i])
				else:
					y.append(r[i])
			else:
				y.append(r[i])
			i += 1
		x.sort()
		y.sort()
		print(''.join(x) + p + ''.join(y))
	t -= 1


from collections import Counter
from collections import OrderedDict
for _ in range(int(input())):
	strng = list(map(str, input()))
	substr = list(map(str, input()))
	dct = Counter(strng)
	dct = OrderedDict(sorted(dct.items()))
	out = ''
	flag = 0
	for i in substr:
		if i in dct:
			dct[i] -= 1
	for ele in substr:
		if substr[0] != ele:
			if ord(substr[0]) > ord(ele):
				flag = 1
			break
	for i in dct:
		if i != substr[0]:
			while dct[i] > 0:
				out += i
				dct[i] -= 1
		elif flag == 0:
			while dct[i] > 0:
				out += i
				dct[i] -= 1
			out += ''.join(substr)
		else:
			out += ''.join(substr)
			while dct[i] > 0:
				out += i
				dct[i] -= 1
	print(out)


t = int(input())
for i in range(t):
	s = input()
	p = input()
	s1 = list(s)
	front = []
	middle = ''
	last = []
	for i in p:
		if i in s1:
			s1.remove(i)
	for i in range(len(s1)):
		if s1[i] < p[0]:
			front.append(s1[i])
		elif s1[i] == p[0]:
			middle += s1[i]
		else:
			last.append(s1[i])
	front.sort()
	front = ''.join(map(str, front))
	last.sort()
	last = ''.join(map(str, last))
	print(min(front + middle + p + last, front + p + middle + last))


import math

def L():
	return list(map(int, input().split()))

def M():
	return map(int, input().split())

def I():
	return int(input())

def S():
	return input()

def twoD(row):
	return [L() for i in range(row)]

def fill(val, size):
	return [val] * size

def strToList(s):
	return [s[i] for i in range(len(s))]

def printList(a):
	[print(i, end=' ') for i in a]
	print()

def binary(a):
	return bin(a)[2:]

def decimal(s):
	a = 0
	n = len(s)
	for i in range(n - 1, -1, -1):
		a += int(s[i]) * 2 ** (n - 1 - i)
	return a
for _ in range(I()):
	s = S()
	p = S()
	d = {chr(i): 0 for i in range(97, 123)}
	for i in s:
		d[i] += 1
	for i in p:
		d[i] -= 1
	ans1 = ''
	ans2 = ''
	for (i, j) in d.items():
		if i < p[0]:
			ans1 += i * j
		if i <= p[0]:
			ans2 += i * j
	ans1 += p
	ans2 += p
	for (i, j) in d.items():
		if i >= p[0]:
			ans1 += i * j
		if i > p[0]:
			ans2 += i * j
	print(min(ans1, ans2))


try:
	t = int(input())
	for _ in range(t):
		s1 = input()
		p1 = input()
		s = list(s1)
		p = list(p1)
		for i in range(len(p)):
			if p[i] in s:
				s.remove(p[i])
		first = ''
		middle = ''
		last = ''
		for i in range(len(s)):
			if s[i] < p1[0]:
				first += s[i]
			elif s[i] == p1[0]:
				middle += s[i]
			elif s[i] > p1[0]:
				last += s[i]
		first = ''.join(sorted(first))
		last = ''.join(sorted(last))
		print(min(first + middle + p1 + last, first + p1 + middle + last))
except:
	pass


import collections
for _ in range(int(input())):
	s = str(input())
	p = str(input())
	v = collections.Counter(s)
	for i in p:
		v[i] -= 1
	k = p[0]
	(r, g, f) = ('', '', '')
	l = [chr(i) for i in range(97, ord(k))]
	l2 = [chr(i) for i in range(ord(k) + 1, ord('z') + 1)]
	for i in l:
		if v[i] > 0:
			r += i * v[i]
	for i in l2:
		if v[i] > 0:
			g += i * v[i]
	if v[k] > 0:
		f = k * v[k]
	print(min(r + f + p + g, r + p + f + g))


t = int(input())
for j in range(t):
	s = input()
	p = input()
	s1 = list(s)
	p1 = list(p)
	for i in p1:
		if i in s1:
			s1.remove(i)
	f = ''
	l = ''
	e = ''
	for k in s1:
		if k < p[0]:
			f += k
		elif k == p[0]:
			e += k
		else:
			l += k
	f = ''.join(sorted(f))
	l = ''.join(sorted(l))
	ans = min(f + e + p + l, f + p + e + l)
	print(ans)


from collections import defaultdict as dd
for _ in range(int(input())):
	s = input()
	p = input()
	d1 = dd(int)
	d2 = dd(int)
	for c in p:
		d1[c] += 1
	for c in s:
		if d1[c] > 0:
			d1[c] -= 1
		else:
			d2[c] += 1
	ans = [(p, p)]
	for k in d2:
		ans.append((k * d2[k], k * len(p)))
	ans.sort(key=lambda x: x[1])
	(ans, _) = list(zip(*ans))
	print(''.join(ans))


for _ in range(int(input())):
	s = input()
	p = input()
	c = {}
	d = {}
	for i in range(97, 124):
		c[chr(i)] = 0
		d[chr(i)] = 0
	l = sorted(list(s))
	m = sorted(list(p))
	for i in l:
		c[i] += 1
	for i in m:
		d[i] += 1
	for i in d:
		c[i] -= d[i]
	ans1 = ''
	ans2 = ''
	for i in c:
		if i < p[0]:
			ans1 += i * c[i]
	ans1 += p
	for i in c:
		if i >= p[0]:
			ans1 += i * c[i]
	for i in c:
		if i <= p[0]:
			ans2 += i * c[i]
	ans2 += p
	for i in c:
		if i > p[0]:
			ans2 += i * c[i]
	print(min(ans1, ans2))


t = int(input())
for _ in range(t):
	s = input()
	p = input()
	g = list(s)
	left = []
	right = []
	mid = []
	for i in p:
		g.remove(i)
	s = ''.join(g)
	for i in s:
		if i > p[0]:
			right.append(i)
		elif i == p[0]:
			mid.append(i)
		else:
			left.append(i)
	left.sort()
	right.sort()
	ans = min(''.join(left) + p + ''.join(mid) + ''.join(right), ''.join(left) + ''.join(mid) + p + ''.join(right))
	print(ans)


for _ in range(int(input())):
	a = list(input())
	b = list(input())
	for i in b:
		a.remove(i)
	a.sort()
	left = []
	right = []
	equal = []
	k = len(a)
	l = 0
	for i in range(1, len(b)):
		if ord(b[i]) > ord(b[0]):
			l = 0
			break
		if ord(b[i]) < ord(b[0]):
			l = 1
			break
	for i in range(len(a)):
		if ord(a[i]) > ord(b[0]):
			k = i
			break
		if ord(a[i]) == ord(b[0]):
			equal.append(b[0])
		elif ord(a[i]) < ord(b[0]):
			left.append(a[i])
	right = a[k:]
	if l:
		print(''.join(left) + ''.join(b) + ''.join(equal) + ''.join(right))
	else:
		print(''.join(left) + ''.join(equal) + ''.join(b) + ''.join(right))


from collections import Counter
for _ in range(int(input())):
	s = input()
	p = input()
	s1 = sorted(s)
	s1 = list(s1)
	ans1 = ''
	ans2 = ''
	cc = Counter(s)
	pc = Counter(p)
	c = {}
	for i in range(97, 124):
		c[chr(i)] = 0
	for ele in cc:
		c[ele] += cc[ele]
	for ele in pc:
		c[ele] -= pc[ele]
	for i in c:
		if i < p[0] and c[i] > 0:
			ans1 += i * c[i]
	ans1 += p
	for i in c:
		if i >= p[0] and c[i] > 0:
			ans1 += i * c[i]
	for i in c:
		if i <= p[0] and c[i] > 0:
			ans2 += i * c[i]
	ans2 += p
	for i in c:
		if i > p[0] and c[i] > 0:
			ans2 += i * c[i]
	print(min(ans1, ans2))


for _ in range(int(input())):
	s = input()
	a = input()
	g = list(a)
	b = []
	l = []
	r = []
	for i in s:
		if i in g:
			g.remove(i)
		elif i > a[0]:
			r.append(i)
		elif i == a[0]:
			b.append(i)
		else:
			l.append(i)
	l.sort()
	r.sort()
	print(min(''.join(l) + a + ''.join(b) + ''.join(r), ''.join(l) + ''.join(b) + a + ''.join(r)))


for i in range(int(input())):
	S = input()
	P = input()
	s = list(S)
	p = list(P)
	for i in p:
		s.remove(i)
	s.sort()
	if p[0] not in s:
		r = s[:]
		r.append(p[0])
		r.sort()
		n = r.index(p[0])
		u = s[:n] + p
		s = s[n:]
		print(*u + s, sep='')
	else:
		r = s[:]
		r.append(p[0])
		y = s.count(p[0])
		r.sort()
		n = r.index(p[0])
		u = ''.join(s[:n + y]) + ''.join(p) + ''.join(s[y + n:])
		y = s.index(p[0])
		q = ''.join(s[:y]) + ''.join(p) + ''.join(s[y:])
		print(min(u, q))


t = int(input())
for _ in range(t):
	a = input()
	b = input()
	n = len(a)
	m = len(b)
	i = 0
	flag = True
	while i + 1 < m and b[i + 1] == b[i]:
		i += 1
	if i < m - 1 and ord(b[i]) < ord(b[i + 1]):
		flag = False
	c = []
	for i in range(0, 26):
		c.append(0)
	for i in range(0, n):
		c[ord(a[i]) - ord('a')] += 1
	for i in range(0, m):
		c[ord(b[i]) - ord('a')] -= 1
	ans = ''
	for i in range(0, 26):
		if i + ord('a') != ord(b[0]):
			ans += chr(i + ord('a')) * c[i]
		elif flag:
			ans += b
			ans += chr(i + ord('a')) * c[i]
		else:
			ans += chr(i + ord('a')) * c[i]
			ans += b
	print(ans)


from collections import Counter
for i in range(int(input())):
	s1 = list(map(str, input()))
	s2 = input()
	p = list(s2)
	A = ''
	B = ''
	C = ''
	s1 = list((Counter(s1) - Counter(p)).elements())
	s1.sort()
	for i in s1:
		if i < s2[0]:
			A += i
		elif i == p[0]:
			B += i
		else:
			C += i
	st1 = B + s2
	st2 = s2 + B
	if st2 < st1:
		B = st2
	else:
		B = st1
	print(A + B + C)


t = int(input())
for _ in range(t):
	string = list(input())
	pattern = list(input())
	for i in pattern:
		string.remove(i)
	string.sort()
	new_st = ''.join(string)
	pattern = ''.join(pattern)
	p = len(pattern)
	l = len(new_st)
	i = 0
	while i < l and new_st[i] < pattern[0]:
		i += 1
	new_st1 = new_st[0:i] + pattern + new_st[i:]
	i = 0
	while i < l and new_st[i] <= pattern[0]:
		i += 1
	new_st2 = new_st[0:i] + pattern + new_st[i:]
	print(min(new_st1, new_st2))


from collections import defaultdict as dd

def solve_func(a, b):
	alphabets_dict = dd(int)
	for loop_var1 in a:
		alphabets_dict[loop_var1] += 1
	for loop_var1 in b:
		alphabets_dict[loop_var1] -= 1
	alphabets = list(alphabets_dict.keys())
	var1 = var2 = ''
	alphabets.sort()
	for loop_var1 in alphabets:
		if loop_var1 == b[0]:
			var1 = var1 + loop_var1 * alphabets_dict[loop_var1]
		elif loop_var1 < b[0]:
			var1 = var1 + loop_var1 * alphabets_dict[loop_var1]
			var2 = var2 + loop_var1 * alphabets_dict[loop_var1]
	var1 += b
	var2 += b
	for loop_var1 in alphabets:
		if loop_var1 == b[0]:
			var2 = var2 + loop_var1 * alphabets_dict[loop_var1]
		elif loop_var1 > b[0]:
			var1 = var1 + loop_var1 * alphabets_dict[loop_var1]
			var2 = var2 + loop_var1 * alphabets_dict[loop_var1]
	if var1 > var2:
		return var2
	else:
		return var1
for i in range(int(input())):
	a = input()
	b = input()
	print(solve_func(a, b))


t = int(input())
while t != 0:
	s = input()
	p = input()
	x = len(s)
	y = len(p)
	a = [0] * 26
	b = [0] * 26
	for i in range(x):
		pointer = ord(s[i]) - 97
		a[pointer] += 1
	for i in range(y):
		pointer = ord(p[i]) - 97
		b[pointer] += 1
	for i in range(26):
		if i + 97 == ord(p[0]):
			x = p[0]
			c_x = a[i] - b[i]
			temp_p1 = p
			for s in range(c_x):
				temp_p1 += x
			temp_p2 = ''
			for s in range(c_x):
				temp_p2 += x
			temp_p2 += p
			if temp_p2 > temp_p1:
				check = 1
			else:
				check = 0
			if check == 1:
				for j in range(26):
					a[j] = a[j] - b[j]
					b[j] = 0
				print(p, end='')
				times = a[i] - b[i]
				while times:
					print(chr(i + 97), end='')
					times -= 1
			else:
				times = a[i] - b[i]
				while times:
					print(chr(i + 97), end='')
					times -= 1
				for j in range(26):
					a[j] = a[j] - b[j]
					b[j] = 0
				print(p, end='')
		else:
			times = a[i] - b[i]
			while times:
				print(chr(i + 97), end='')
				times -= 1
	t -= 1
	print(end='\n')


t = int(input())
for _ in range(t):
	s = list(input())
	p = list(input())
	freq = {}
	for c in s:
		freq[c] = freq.get(c, 0) + 1
	for c in p:
		freq[c] -= 1
	flag = 0
	for i in range(len(p) - 1):
		if p[i] == p[i + 1]:
			continue
		if p[i] > p[i + 1]:
			flag = 1
		break
	res = []
	for (key, value) in sorted(freq.items(), key=lambda x: x[0]):
		if key < p[0] or key > p[0]:
			res.append(key * value)
		elif key == p[0]:
			if flag == 0:
				res.append(key * value)
				res.append(''.join(p))
			else:
				res.append(''.join(p))
				res.append(key * value)
	print(''.join(res))


import math
t = int(input())
while t > 0:
	arr = {}
	h = sorted(input())
	p = input()
	for i in h:
		if i in arr.keys():
			arr[i] += 1
		else:
			arr[i] = 1
	for i in p:
		if i in arr.keys():
			arr[i] -= 1
	str = ''
	flag = 0
	for i in range(len(p) - 1):
		if p[i] < p[i + 1]:
			flag = 0
			break
		if p[i] > p[i + 1]:
			flag = 1
			break
	for i in arr.keys():
		if i == p[0]:
			if flag:
				str += p
				str += i * arr[i]
			else:
				str += i * arr[i]
				str += p
			continue
		str += i * arr[i]
	print(str)
	t = t - 1


from copy import deepcopy
for _ in range(int(input())):
	s = list(input())
	p = list(input())
	for i in p:
		s.remove(i)
	s.sort()
	ne = deepcopy(s)
	ne.append(p[0])
	ne = sorted(ne, reverse=True)
	if p[0] not in s:
		print(''.join(s[0:len(ne) - ne.index(p[0]) - 1]) + ''.join(p) + ''.join(s[len(ne) - ne.index(p[0]) - 1:]))
	else:
		air = ''.join(s[0:s.index(p[0])]) + ''.join(p) + ''.join(s[s.index(p[0]):])
		print(min(air, ''.join(s[0:len(ne) - ne.index(p[0]) - 1]) + ''.join(p) + ''.join(s[len(ne) - ne.index(p[0]) - 1:])))