Олимпиадный тренинг

Задача . A. Вставь цифру


Задача

Темы: жадные алгоритмы математика Строки *800

У вас есть положительное число длины \(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 
765443
10
544
6666
613579
987531
98765443210123456789
773737
210000000
70589590
8281271277321

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w643
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет