← 返回题目列表

Codeforces · 670/F

F. 恢复号码

中文机器翻译题面 查看原题

Vasya 决定将一个非常大的整数 n 传递给 Kate。首先,他将该数字写为字符串,然后附加到正确的整数 k(n 中的位数)。

神奇的是,当这张纸条被传递给凯特时,所有数字都以任意顺序打乱。 Vasya 唯一记得的是 n 的非空子串(n 的子串是数字 n 的连续数字序列)。

Vasya 知道可能有不止一种方法可以恢复数字 n。你的任务是找到尽可能小的初始整数n。请注意,数字 n 的十进制表示形式不包含前导零,除非整数 n 本身等于零(在这种情况下使用单个数字 0)。

输入

输入的第一行包含 Kate 收到的字符串。该字符串中的位数不超过 1 000 000。

第二行包含 Vasya 记住的 n 的子字符串。该字符串可以包含前导零。

保证输入数据正确,答案始终存在。

输出

打印 Vasya 可以传递给 Kate 的小整数 n。

示例

输入 #1

003512
021

输出 #1

30021

输入 #2

199966633300
63

输出 #2

3036366999