time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
You have apositivenumber of lengthn�and one additional digit.
You can insert this digit anywhere in the number, including at the beginning or at the end.
Your task is to make the result as large as possible.
For example, you have the number7654376543, and the additional digit is44. Then the maximum number you can get is765443765443, and it can be obtained in two ways — by inserting a digit after the33th or after the44th digit of the number.
Input
The first line contains a single integert�(1≤t≤1041≤�≤104) — the number of test cases.
The descriptions of the test cases follow.
The first line of the description of each test case contains two integersn�andd�(1≤n≤2⋅1051≤�≤2⋅105;0≤d≤90≤�≤9) — the length of the number and an additional digit, respectively.
The second line of the description of each test case contains a string consisting ofn�digits — the number that you have initially. It is guaranteed that the number does not contain leading zeros.
It is guaranteed that the sum ofn�for all test cases does not exceed2⋅1052⋅105.
Output
For each test case, output a string consisting ofn+1�+1digits — the maximum possible number that can be obtained.
Example
input
Copy
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
output
Copy
76544310544666661357998753198765443210123456789773737210000000705895908281271277321
7
解题说明：此题是一道数学题，为了让数字最大，很显然数字从大到小排列才是最大的，对数组遍历，让插入的数字与当前数字比较，如果比当前数字大就放前面，否则就放到最后。
#include char s[200002];int main() {int t;scanf("%d", &t);while (t--){int n, d;scanf("%d %d", &n, &d);scanf("%s", s);d += '0';int i;for (i = 0; i < n; i++){if (s[i] i; j--){s[j] = s[j - 1];}s[i] = d;puts(s);}return 0;}