← 返回题目列表

Codeforces · 1811/A

A. 插入数字

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

您有一个长度为 $$$n$$$ 的正数和一位附加数字。

您可以在号码中的任意位置插入该数字,包括开头或结尾。

你的任务是使结果尽可能大。

例如,您的号码为 $$$76543$$$,附加数字为 $$$4$$$。那么你能得到的最大数字是$$$765443$$$,可以通过两种方式获得——在数字的第$$$3$$$后面或第$$$4$$$数字后面插入一个数字。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

测试用例的描述如下。

每个测试用例描述的第一行包含两个整数 $$$n$$$ 和 $$$d$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$0 \le d \le 9$$$) — 分别是数字的长度和附加数字。

每个测试用例描述的第二行包含一个由 $$$n$$$ 数字组成的字符串 - 您最初拥有的数字。确保该数字不包含前导零。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个由 $$$n + 1$$$ 数字组成的字符串 - 可以获得的最大可能数字。

示例

输入 #1

11
5 4
76543
1 0
1
2 5
44
3 6
666
5 6
13579
5 8
97531
19 4
9876543210123456789
5 7
73737
8 1
20000000
7 0
7058959
12 1
828127127732

输出 #1

765443
10
544
6666
613579
987531
98765443210123456789
773737
210000000
70589590
8281271277321