CF670F Restore a Number

Vasya 决定把一个非常大的整数 $n$ 传递给 Kate。首先，他将该数字写成一个字符串，然后在右侧添加了整数 $k$ —— 即 $n$ 的位数。 神奇的是，在将这张纸条传给 Kate 的过程中，所有数字都被随意打乱了顺序。Vasya 只记得 $n$ 的一个非空子串（即 $n$ 中若干连续的数字）。 Vasya 知道，恢复 $n$ 的方式可能不止一种。你的任务是找到可能的最小初始整数 $n$。注意，$n$ 的十进制表示不含前导零，除非 $n=0$（在这种情况下使用单独的数字 $0$）。

输入的第一行是 Kate 收到的字符串。该字符串的长度不超过 $1000000$。 第二行是 Vasya 记得的 $n$ 的子串。这个字符串可能包含前导零。 保证输入数据合法且答案一定存在。

输出 Vasya 可能传递给 Kate 的最小整数 $n$。

由 ChatGPT 5 翻译