Вам дана бинарная строка длины \(n\) (т. е. строка, состоящая из \(n\) символов '0' и '1').
За один ход вы можете поменять местами два соседних символа в строке. Какую лексикографически минимальную строку вы можете получить из заданной, если вы можете сделать не более, чем \(k\) ходов? Возможно, что вы не сделаете ни одного хода.
Заметьте, что вы можете менять местами одну и ту же пару соседних символов с индексами \(i\) и \(i+1\) любое (возможно, нулевое) количество раз. Каждый такой обмен является отдельным ходом.
Вам необходимо ответить на \(q\) независимых наборов входных данных.
Выходные данные
Для каждого запроса выведите ответ на него — лексикографически минимальную возможную строку длины \(n\), которую вы можете получить из заданной, сделав не более, чем \(k\) ходов.
Примечание
В первом тестовом примере вы можете изменить строку следующим образом: \(1\underline{10}11010 \rightarrow \underline{10}111010 \rightarrow 0111\underline{10}10 \rightarrow 011\underline{10}110 \rightarrow 01\underline{10}1110 \rightarrow 01011110\).
В третьем тестовом примере у вас есть достаточно ходов для того, чтобы сделать строку отсортированной.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
8 5
11011010
7 9
1111100
7 11
1111100
|
01011110
0101111
0011111
|