Vasya decided to pass a very large integer n to Kate. First, he wrote that number as a string, then he appended to the right integer k — the number of digits in n. 

Magically, all the numbers were shuffled in arbitrary order while this note was passed to Kate. The only thing that Vasya remembers, is a non-empty substring of n (a substring of n is a sequence of consecutive digits of the number n).

Vasya knows that there may be more than one way to restore the number n. Your task is to find the smallest possible initial integer n. Note that decimal representation of number n contained no leading zeroes, except the case the integer n was equal to zero itself (in this case a single digit 0 was used).


-----Input-----

The first line of the input contains the string received by Kate. The number of digits in this string does not exceed 1 000 000.

The second line contains the substring of n which Vasya remembers. This string can contain leading zeroes. 

It is guaranteed that the input data is correct, and the answer always exists.


-----Output-----

Print the smalles integer n which Vasya could pass to Kate.


-----Examples-----
Input
003512
021

Output
30021

Input
199966633300
63

Output
3036366999

Difficulty: HARD
Tags: String algorithms

Complete search

Constructive algorithms
Skill types: Complete search

Starter code:

Solutions:
import math
from collections import Counter
s = list(map(int, input()))
substr = input().rstrip()
t = list(map(int, substr))
m = len(s)
(x, y) = (0, m)
z = (x + y) // 2
while z != x:
	if z + math.floor(math.log10(z)) + 1 <= m:
		x = z
	else:
		y = z
	z = (x + y) // 2
m1 = z
k = math.floor(math.log10(m1)) + 1
D = Counter(s)
D.subtract(list(map(int, str(m1))))
D.subtract(t)
try:
	c1 = min((i for i in range(1, 10) if D[i] > 0))
	c2 = t[0]
	D[c1] -= 1
	_prefix = [c1]
	for c in range(c2):
		_prefix += [c] * D[c]
	_suffix = []
	for c in range(c2 + 1, 10):
		_suffix += [c] * D[c]
	num = ''.join([str(c2)] * D[c2])
	prefix = ''.join(map(str, _prefix))
	suffix = ''.join(map(str, _suffix))
	if c2 == 0:
		print(min(prefix + substr + num + suffix, prefix + num + substr + suffix))
	else:
		D[c1] += 1
		st = []
		for c in range(10):
			st += [c] * D[c]
		print(min(prefix + substr + num + suffix, prefix + num + substr + suffix, substr + ''.join(map(str, st))))
except ValueError:
	print(substr + '0' * D[0])


def main():
	s = input()
	if s in ('01', '10'):
		print(0)
		return
	cnt = [0] * 58
	for j in map(ord, s):
		cnt[j] += 1
	(n, s1) = (sum(cnt), input())
	for le in range(n - 1, 0, -1):
		if len(str(le)) + le == n:
			break
	for s in (s1, str(le)):
		for j in map(ord, s):
			cnt[j] -= 1
	res = [''.join([s1] + [chr(i) * a for (i, a) in enumerate(cnt) if a])] if s1[0] > '0' else []
	for i in range(49, 58):
		if cnt[i]:
			cnt[i] -= 1
			l = [chr(i) * a for (i, a) in enumerate(cnt) if a]
			l.append(s1)
			res.append(''.join([chr(i)] + sorted(l)))
			break
	print(min(res))
main()


a = input()
b = input()
d = [0] * 10
n = 0
for j in range(1000100):
	t = str(j)
	if len(t) + j == len(a):
		n = j
for x in str(n):
	d[ord(x) - ord('0')] -= 1
for x in a:
	d[ord(x) - ord('0')] += 1
for x in b:
	d[ord(x) - ord('0')] -= 1
if sum(d) == 0:
	print(b)
else:
	A = []
	B = []
	C = []
	D = []
	if b[0] != '0':
		A = list(b)
		for j in range(10):
			for k in range(d[j]):
				A.append(chr(ord('0') + j))
	t = 1
	while t < len(d) and d[t] == 0:
		t += 1
	oo = ord('0')
	if t < len(d):
		B.append(chr(oo + t))
		d[t] -= 1
		for j in range(ord(b[0]) - oo):
			for k in range(d[j]):
				B.append(chr(ord('0') + j))
		B.extend(list(b))
		for j in range(ord(b[0]) - oo, 10):
			for k in range(d[j]):
				B.append(chr(ord('0') + j))
		C.append(chr(oo + t))
		for j in range(min(ord(b[0]) - oo + 1, 10)):
			for k in range(d[j]):
				C.append(chr(ord('0') + j))
		C.extend(list(b))
		for j in range(ord(b[0]) - oo + 1, 10):
			for k in range(d[j]):
				C.append(chr(ord('0') + j))
	ans = []
	if len(A) > 0:
		ans.append(''.join(A))
	if len(B) > 0:
		ans.append(''.join(B))
	if len(C) > 0:
		ans.append(''.join(C))
	print(min(ans))


import sys
sys.stderr = sys.stdout
from collections import Counter
K = (0, 11, 102, 1003, 10004, 100005, 1000006)

def sf(S, C, C0):
	if C0 == '0':
		return True
	if S[0] == '0':
		return False

	def g1():
		yield from S
		for _ in range(C['0']):
			yield '0'
		for _ in range(C[C0]):
			yield C0

	def g2():
		yield C0
		for _ in range(C['0']):
			yield '0'
		for _ in range(C[C0] - 1):
			yield C0
		yield from S
	for (d1, d2) in zip(g1(), g2()):
		if d1 < d2:
			return True
		elif d1 > d2:
			return False
	return True

def number(D, S):
	m = len(D)
	for i in range(len(K)):
		if K[i] > m:
			k = m - i
			break
	sK = str(k)
	if len(S) == k:
		return S
	C = Counter(D)
	C.subtract(sK)
	C.subtract(S)
	L = []
	C0 = next((d for d in '1234567890' if C[d]))
	if sf(S, C, C0):
		L.append(S)
		for d in '0123456789':
			L.append(d * C[d])
	else:
		L.append(C0)
		C[C0] -= 1
		S0 = S[0]
		for d in '0123456789':
			if d == S0:
				S1 = next((d for d in S if d != S0), S0)
				if S1 <= S0:
					L.append(S)
					L.append(d * C[d])
				else:
					L.append(d * C[d])
					L.append(S)
			else:
				L.append(d * C[d])
	return ''.join(L)

def main():
	D = input()
	S = input()
	print(number(D, S))

def readint():
	return int(input())

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

def readintt():
	return tuple(readinti())

def readintl():
	return list(readinti())

def readinttl(k):
	return [readintt() for _ in range(k)]

def readintll(k):
	return [readintl() for _ in range(k)]

def log(*args, **kwargs):
	print(*args, **kwargs, file=sys.__stderr__)
main()


import sys

def main():
	a = sys.stdin.readline().strip()
	b = sys.stdin.readline().strip()
	if a == '01' or a == '10':
		print('0')
		return
	cnt = [0] * 256
	for i in map(ord, a):
		cnt[i] += 1
	n = sum(cnt)
	l = 0
	for i in range(1, 8):
		if i == len(str(n - i)):
			l = n - i
			break
	for s in (b, str(l)):
		for i in map(ord, s):
			cnt[i] -= 1
	res = [''.join([b] + [chr(k) * v for (k, v) in enumerate(cnt) if v > 0])] if b[0] > '0' else []
	for i in range(ord('1'), ord('9') + 1):
		if cnt[i] > 0:
			cnt[i] -= 1
			others = [chr(k) * v for (k, v) in enumerate(cnt) if v > 0]
			others.append(b)
			res.append(''.join([chr(i)] + sorted(others)))
			break
	print(min(res))
main()