You are given an integer a that consists of n digits. You are also given a sequence of digits s of length m. The digit in position j (1 ≤ j ≤ m) of sequence s means that you can choose an arbitrary position i (1 ≤ i ≤ n) in a and replace the digit in the chosen position i with sj. Each element in the sequence s can participate in no more than one replacing operation.

Your task is to perform such sequence of replacements, that the given number a gets maximum value. You are allowed to use not all elements from s.

Input

The first line contains positive integer a. Its length n is positive and doesn't exceed 105. The second line contains sequence of digits s. Its length m is positive and doesn't exceed 105. The digits in the sequence s are written consecutively without any separators.

The given number a doesn't contain leading zeroes. 

Output

Print the maximum value that can be obtained from a after a series of replacements. You are allowed to use not all elements from s. The printed number shouldn't contain any leading zeroes.

Examples

Input

1024
010


Output

1124


Input

987
1234567


Output

987

Difficulty: EASY
Tags: Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
n = str(input())
s = str(input())
ref = 10 * [0]
for j in range(len(s)):
	index = ord(s[j]) - 48
	ref[index] += 1
for j in range(len(n)):
	output = n[j]
	num = ord(n[j]) - 48
	for k in range(9, num, -1):
		if ref[k] > 0:
			output = str(k)
			ref[k] -= 1
			break
	print(end=output)


a = input()
s = input()
(a, lst, ind, t) = (list(a), list(s), 0, '')
lst.sort(reverse=True)
for i in range(len(a)):
	if lst[ind] > a[i]:
		a[i] = lst[ind]
		ind += 1
	if ind == len(lst):
		break
for elem in a:
	t += elem
print(t)


first = list(map(int, list(input())))
second = list(sorted(map(int, list(input())), key=lambda x: x, reverse=True))
second.append(0)
ptr2 = 0
for i in range(len(first)):
	if first[i] < second[ptr2]:
		first[i] = second[ptr2]
		ptr2 += 1
	print(first[i], end='')


a = list(input())
b = sorted(list(input()))[::-1]
j = 0
for i in range(len(a)):
	if b[j] > a[i]:
		a[i] = (b[j], a[i])
		j += 1
		if j >= len(b):
			break
for i in a:
	print(i[0], end='')


a = [i for i in input()]
b = sorted([i for i in input()], reverse=True)
(i, p) = (0, 0)
while i < len(a) and p < len(b):
	if a[i] < b[p]:
		a[i] = b[p]
		p += 1
	i += 1
print(''.join(a))


i = 0
j = 0
a = list(input())
b = sorted(input())[::-1]
while i < len(a) and j < len(b):
	if a[i] < b[j]:
		a[i] = b[j]
		j += 1
	i += 1
print(*a, sep='')


n = list(input())
m = sorted(input())
a = len(m)
for i in range(len(n)):
	if n[i] < m[a - 1]:
		n[i] = m[a - 1]
		a = a - 1
		if a == 0:
			break
print(''.join(n))


s = input()
b = list(s)
t = input()
a = list(t)
a = sorted(a, reverse=True)
j = 0
i = 0
while i < len(b) and j < len(a):
	if b[i] < a[j]:
		b[i] = a[j]
		j = j + 1
		i = i + 1
	else:
		i = i + 1
		pass
print(''.join(b))


def s():
	a = list(input())
	s = list(input())
	s.append('0')
	s.sort(reverse=True)
	it = iter(s)
	q = next(it)
	for (i, v) in enumerate(a):
		if q > v:
			a[i] = q
			q = next(it)
	print(*a, sep='')
s()


s = list(input())
a = list(input())
a.sort(reverse=True)
(ai, si) = (0, 0)
while ai < len(a) and si < len(s):
	if s[si] < a[ai]:
		s[si] = a[ai]
		a.pop(ai)
	si += 1
print(''.join(s))


a = list((int(x) for x in input()))
b = list((int(x) for x in input()))
b.sort()
b.reverse()
c = ''
for x in range(len(a)):
	if len(b) > 0 and a[x] < b[0]:
		a[x] = b[0]
		b.pop(0)
	c += str(a[x])
print(c)


a = [int(n) for n in input()]
s = [int(n) for n in input()]
s.sort(reverse=True)
for (i, n) in enumerate(a):
	if len(s) == 0:
		break
	if len(s) > 0 and s[0] > n:
		a[i] = s[0]
		del s[0]
print(''.join(map(str, a)))


a = list(input())
s = list(input())
s.sort(reverse=True)
(aindex, sindex) = (0, 0)
while sindex < len(s) and aindex < len(a):
	if s[sindex] > a[aindex]:
		a[aindex] = s[sindex]
		s.pop(sindex)
		sindex = 0
		aindex += 1
	else:
		aindex += 1
print(''.join(a))


s = input().rstrip()
d = list(map(int, list(input().rstrip())))
d.sort()
d = d[::-1]
i = 0
ans = ''
for j in range(len(s)):
	if i < len(d) and int(s[j]) < d[i]:
		ans += str(d[i])
		i += 1
	else:
		ans += s[j]
print(ans)


a = input()
a = list(a)
s = input()
s = list(s)
s.sort(reverse=True)
c = 0
i = 0
j = 0
while i < len(s) and j < len(a) and (c < len(s)):
	if s[i] > a[j]:
		a[j] = s[i]
		j += 1
		i += 1
	else:
		j += 1
for i in range(len(a)):
	print(a[i], end='')


import sys, math
I = input
j = i = 0
a = list(I())
b = sorted(I())[::-1]
while i < len(a) and j < len(b):
	if a[i] < b[j]:
		a[i] = b[j]
		j += 1
	i += 1
print(''.join(a))


I = input
(a, s, q) = ([*I()], I(), {})
for i in s:
	if i in q:
		q[i] += 1
	else:
		q[i] = 1
for i in range(len(a)):
	for j in range(9, 0, -1):
		j = str(j)
		if j in q:
			if j > a[i] and q[j]:
				a[i] = j
				q[j] -= 1
				break
print(''.join(a))


def main():
	(s, a) = (list(input()), sorted(input(), reverse=True))
	j = 0
	for (i, x) in enumerate(s):
		if j >= len(a):
			break
		if int(x) < int(a[j]):
			s[i] = a[j]
			j += 1
	print(''.join(s))
main()


A = list(input())
S = list(input())
S.sort()
for (i, v) in enumerate(A):
	if S == []:
		break
	if v < S[-1]:
		A[i] = S[-1]
		S.pop()
print(''.join(A))


a = list(input())
s = list(input())
n = len(a)
m = len(s)
dict_ = {}
for j in range(9, 0, -1):
	if s.count(str(j)) != 0:
		dict_[str(j)] = s.count(str(j))
for i in range(n):
	for key in dict_:
		if key <= a[i]:
			break
		elif key > a[i] and dict_[key] > 0:
			a[i] = key
			dict_[key] -= 1
			if dict_[key] == 0:
				del dict_[key]
			break
print(''.join(a))


import sys
import string
from collections import Counter, defaultdict
from math import fsum, sqrt, gcd, ceil, factorial
from itertools import combinations, permutations
flush = lambda : sys.stdout.flush
comb = lambda x, y: factorial(x) // factorial(y) // factorial(x - y)
ip = lambda : input()
ii = lambda : int(input())
r = lambda : map(int, input().split())
rr = lambda : list(r())
a = list(ip())
b = list(ip())
b.sort(reverse=True)
c = 0
for (i, j) in enumerate(a):
	if c < len(b) and j < b[c]:
		a[i] = b[c]
		c += 1
print(''.join(a))


a = list(input())
s = list(input())
s.sort(reverse=True)
j = 0
for i in range(len(a)):
	if int(a[i]) < int(s[j]) and j < len(s):
		a[i] = s[j]
		j = j + 1
	if j >= len(s):
		break
print(''.join(a))


A = list(input())
i = 0
for d in sorted(input(), reverse=True):
	while i < len(A) and A[i] >= d:
		i += 1
	if i == len(A):
		break
	A[i] = d
print(*A, sep='')


import re
import sys

def to_matrix(l, n):
	return [l[i:i + n] for i in range(0, len(l), n)]

def array_to_string(l):
	s = ''
	for i in l:
		s += str(i)
	return s
lst = []
for line in sys.stdin:
	lst.append(line.rstrip('\n'))
matrix = to_matrix(lst, 2)
digitos = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
for m in matrix:
	n = [int(i) for i in list(m[0])]
	_min = min(n)
	for i in m[1]:
		digitos[int(i)] += 1
	i = 0
	j = 9
	while i < len(n) and j > 0:
		while i < len(n) and j > 0 and (digitos[j] > 0):
			if j > n[i]:
				n[i] = j
				digitos[j] -= 1
			i += 1
		j -= 1
	print(array_to_string(n))


def f():
	t = list(input())
	p = sorted(list(input()), reverse=True)
	(j, n) = (0, len(t))
	for i in p:
		while t[j] >= i:
			j += 1
			if j == n:
				return ''.join(t)
		t[j] = i
	return ''.join(t)
print(f())


n = list(input())
s = sorted(input())[::-1]
s_index = 0
for (i, nn) in enumerate(n):
	if s_index >= len(s):
		break
	if int(nn) < int(s[s_index]):
		n[i] = s[s_index]
		s_index += 1
print(''.join(n))


n1 = input()
n2 = input()
n1 = [int(x) for x in n1]
n2 = [int(x) for x in n2]
n2.sort(reverse=True)
i1 = 0
for (i2, v2) in enumerate(n2):
	while i1 < len(n1):
		if v2 > n1[i1]:
			n1[i1] = v2
			i1 = i1 + 1
			break
		i1 = i1 + 1
for i in n1:
	print(i, end='')
print()


original = input().strip()
descending = ''.join(sorted(input().strip(), reverse=True))
newString = ''
index = 0
did_not_finish_index = len(original)
for x in range(len(original)):
	if index >= len(descending):
		did_not_finish_index = x
		break
	if original[x] < descending[index]:
		newString += descending[index]
		index += 1
	else:
		newString += original[x]
for y in range(did_not_finish_index, len(original)):
	newString += original[y]
print(newString)


import datetime
n = list(input())
string = list(input())
string.sort(reverse=True)
for i in range(0, len(n)):
	if n[i] < string[0]:
		n[i] = string[0]
		string.pop(0)
		if len(string) < 1:
			break
print(''.join(n))


import math, sys
from collections import defaultdict, deque
import bisect as bi

def yes():
	print('YES')

def no():
	print('NO')

def I():
	return int(sys.stdin.readline())

def In():
	return map(int, sys.stdin.readline().split())

def Sn():
	return sys.stdin.readline().strip()

def dict(a):
	d = {}
	for x in a:
		if d.get(x, -1) != -1:
			d[x] += 1
		else:
			d[x] = 1
	return d

def find_gt(a, x):
	i = bi.bisect_left(a, x)
	if i != len(a):
		return i
	else:
		return -1

def main():
	try:
		t = Sn()
		l = list(t)
		s = list(Sn())
		t1 = {}
		s1 = {}
		for x in l:
			if t1.get(int(x), -1) != -1:
				t1[int(x)] += 1
			else:
				t1[int(x)] = 1
		for x in s:
			if s1.get(int(x), -1) != -1:
				s1[int(x)] += 1
			else:
				s1[int(x)] = 1
		n = len(l)
		for x in range(n):
			temp = int(l[x])
			ma = temp
			for i in range(temp, 10):
				if s1.get(i, -1) != -1:
					ma = i
			if ma != temp:
				s1[ma] -= 1
				l[x] = str(ma)
				if s1[ma] == 0:
					s1.pop(ma)
		print(''.join(l))
	except:
		pass
M = 998244353
P = 1000000007
for _ in range(1):
	main()


a = input()
s = input()
s = ''.join(sorted(s, reverse=True))
j = 0
for i in range(len(a)):
	if a[i] < s[j]:
		a = a[0:i] + s[j] + a[i + 1:]
		j = j + 1
	if j == len(s):
		break
print(a)


from collections import Counter
a = input()
s = Counter([int(num) for num in input()])
out = ''
for i in range(len(a)):
	tmp = None
	for key in s.keys():
		if key > int(a[i]):
			if not tmp:
				tmp = key
			elif key > tmp:
				tmp = key
	if tmp:
		out += str(tmp)
		s[tmp] -= 1
		if s[tmp] == 0:
			del s[tmp]
	else:
		out += a[i]
print(out)


a = list(map(int, list(input())))
b = sorted(list(map(int, list(input()))))
for i in range(len(a)):
	if len(b) == 0:
		break
	if b[-1] > a[i]:
		a[i] = b.pop()
ans = ''
for c in a:
	ans += str(c)
print(ans)


a = [int(x) for x in input()]
b = sorted([int(y) for y in input()], reverse=True)
y = 0
for i in range(0, len(a)):
	if y < len(b) and a[i] < b[y]:
		a[i] = b[y]
		y = y + 1
print(''.join([str(c) for c in a]))


import sys

def new_num(a, s):
	s.sort()
	mm = s.pop()
	for i in range(len(a)):
		if a[i] < mm:
			a[i] = mm
			if len(s) > 0:
				mm = s.pop()
			else:
				return ''.join(map(str, a))
	return ''.join(map(str, a))

def main():
	s1 = sys.stdin.readline()
	s2 = sys.stdin.readline()
	a = [int(i) for i in s1[:-1]]
	s = [int(j) for j in s2[:-1]]
	sys.stdout.write(new_num(a, s))
	return
main()


a = input()
b = input()
p = list(a)
q = list(b)
q = sorted(q, reverse=True)
for i in range(len(p)):
	l = int(p[i])
	if len(q) != 0:
		k = int(q[0])
	else:
		k = 0
	if k > l:
		p[i] = str(k)
		q.pop(0)
print(''.join(p))


I = input
j = i = 0
a = list(I())
b = sorted(I())[::-1]
while i < len(a) and j < len(b):
	if a[i] < b[j]:
		a[i] = b[j]
		j += 1
	i += 1
print(''.join(a))


a = input()
s = input()
a = [int(x) for x in str(a)]
s = [int(x) for x in str(s)]
s.sort(reverse=True)
final_num = []
for i in range(len(a)):
	m = a[i]
	if len(s) != 0:
		n = s[0]
	else:
		n = 0
	if n > m:
		temp = n
		s.pop(0)
	else:
		temp = m
	final_num.append(str(temp))
print(''.join(final_num))


a = input()
b = sorted(list(map(int, list(input()))), reverse=True)
if len(b) < len(a):
	b = b + [0] * (len(a) - len(b))
n = ''
m = 0
c = len(b)
for x in list(a):
	if b[m] <= int(x):
		n += x
	else:
		n += str(b[m])
		m += 1
print(n)


ind = 0
a = input()
a = list(a)
s = input()
L = list(s)
L.sort(reverse=True)
for i in range(len(a)):
	if L[ind] > a[i]:
		a[i] = L[ind]
		ind += 1
	if ind == len(L):
		break
s = ''
for item in a:
	s += item
print(s)


a = list(input())
b = list(input())
b.sort(reverse=True)
ans = ''
j = 0
for i in range(len(a)):
	if j < len(b) and b[j] > a[i]:
		a[i] = b[j]
		j += 1
print(ans.join(a))


import sys
(s1, s2) = sys.stdin.read().split()
l2 = len(s2)
s2 = sorted(s2)
s1 = list(s1)
i = 0
j = l2 - 1
while j > -1 and i < len(s1):
	while i < len(s1) and s1[i] >= s2[j]:
		i += 1
	if i < len(s1):
		s1[i] = s2[j]
	j -= 1
print(''.join(s1))


main = input()
num = list(map(int, list(input())))
num.sort()
last = ''
c = 0
try:
	for n in main:
		if num[-1] > int(n):
			last += str(num[-1])
			del num[-1]
			c += 1
		else:
			last += n
			c += 1
except:
	last += main[c:]
print(last)


a = list(input())
b = list(input())
b.sort(reverse=True)
(i, j) = (0, 0)
while i < len(a) and j < len(b):
	if a[i] < b[j]:
		a[i] = b[j]
		j += 1
	i += 1
print(''.join(a))


def STR():
	return list(input())

def INT():
	return int(input())

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

def MAP2():
	return map(float, input().split())

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

def STRING():
	return input()
import string
import sys
from heapq import heappop, heappush
from bisect import *
from collections import deque, Counter, defaultdict
from math import *
from itertools import permutations, accumulate
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]
a = STR()
s = STR()
n = len(a)
m = len(s)
if m == 0:
	print(''.join(a))
	exit(0)
s.sort(reverse=True)
j = 0
for i in range(n):
	if j < m and s[j] > a[i]:
		a[i] = s[j]
		j += 1
print(''.join(a))


a = input()
b = input()
x = []
y = []
for item in a:
	x.append(int(item))
for item in b:
	y.append(int(item))
y.sort(reverse=True)
for item in x:
	if len(y) > 0:
		k = y[0]
		if k > item:
			print(k, end='')
			y.remove(k)
		else:
			print(item, end='')
	else:
		print(item, end='')


import sys
a = [x for x in sys.stdin.readline() if x != '\n']
s = sys.stdin.readline()
i = 0
v = [0] * 10
while s[i] != '\n':
	v[int(s[i])] += 1
	i += 1
j = 9
for i in range(len(a)):
	while v[j] == 0 and j > 0:
		j -= 1
	if j > int(a[i]):
		a[i] = str(j)
		v[j] -= 1
print(''.join(a))


a = list(map(int, list(input())))
b = list(map(int, list(input())))
count = 0
b.sort(reverse=True)
for i in range(len(a)):
	if count < len(b):
		if a[i] < b[count]:
			a[i] = b[count]
			count += 1
			continue
	else:
		break
for i in a:
	print(i, end='')


from sys import stdin, stdout
ans = list(map(int, list(stdin.readline().strip())))
d = {}
for f in stdin.readline().strip():
	if int(f) in d:
		d[int(f)] += 1
	else:
		d[int(f)] = 1
for i in range(len(ans)):
	for j in range(10, ans[i], -1):
		if j in d and d[j]:
			ans[i] = j
			d[j] -= 1
			break
stdout.write(''.join(list(map(str, ans))))


n = input()
m = input()
arr = []
for i in m:
	arr.append(int(i))
arr.sort(reverse=True)
st = ''
count = 0
for i in range(len(n)):
	if count >= len(arr):
		st += n[i:]
		break
	elif int(n[i]) < arr[count]:
		st += str(arr[count])
		count += 1
	else:
		st += n[i]
print(st)


import sys, math
a = input()
s = input()
a = list(a)
s = list(s)
s.sort()
s = s[::-1]
(j, i) = (0, 0)
while i < len(a) and j < len(s):
	if j < len(s) and int(s[j]) > int(a[i]):
		a[i] = s[j]
		j += 1
	i += 1
print(''.join(a))


a = input()
b = input()
b = sorted(b)
m = len(b)
b = b[::-1]
j = 0
for i in range(len(a)):
	if int(a[i]) < int(b[j]):
		a = a[:i] + b[j] + a[i + 1:]
		if j == m - 1:
			break
		else:
			j = j + 1
print(a)


(a, s) = (str(input()), str(input()))
d = [0] * 10
for c in s:
	d[ord(c) - ord('0')] += 1
j = max([i for i in range(10) if d[i] > 0])
ans = [ord(c) - ord('0') for c in a]
for i in range(len(a)):
	if j > ans[i]:
		d[j] -= 1
		ans[i] = j
		while j > 0 and d[j] == 0:
			j -= 1
print(''.join([str(x) for x in ans]))