题目描述

在数学竞赛中，参赛者小$\tt Z$ 需要完成一项特殊任务：

给定一个初始数字串 $S$（不含前导零）和一个额外数字 $d（0≤d≤9）$，通过将 $d$ 插入到 $S$ 的任意位置（包括最前和最后），构造出可能的最大数值。

例如：

• 初始数字串：$76543$
• 额外数字：$4$
• 最优解：$765443$（将 $4$ 插入第 $3$ 位或第 $4$ 位后）

输入格式

输入包含两行。

第一行包含两个整数 $n$ 和 $d$，用空格分隔。$n$ 表示初始数字串的长度，$d$ 表示要插入的数字。

第二行输入长度为 $n$ 的数字串 $S$。

输出格式

输出一行，为插入 $d$ 后得到的长度为 $n+1$ 的最大数字串。

输入输出样例

2 5
44

544

样例 $\tt \#1$说明

• 将 $5$ 插入到最前面得到最大值。

7 0
7058959

70589590

样例 $\tt \#2$说明

• 将 $0$ 插入到最后面得到最大值。

12 1
828127127732

8281271277321

数据范围

• 对于 $20\%$ 的数据，$1 \le n \le 10^3，d=0$
• 对于 $100\%$ 的数据，$1 \le n \le 2 \times 10^5, 0\le d \le 9$