Вам дана строка \(s\) из символов 0 и 1. Вы можете делать преобразование следующего вида:
- выбрать непустую сплошную подстроку \(s\), содержащую одинаковое количество символов 0 и 1;
- заменить все символы 0 в подстроке на 1, и наоборот;
- развернуть подстроку.
Например, рассмотрим \(s\) = 00111011, и следующее преобразование:
- Выберем в качестве подстроки первые шесть символов: 00111011. Эту подстроку можно выбрать, поскольку в ней количество 0 и 1 совпадает. Выбирать подстроки 0, 110, или всю строку целиком нельзя.
- Заменим все символы в подстроке на противоположные: 11000111.
- Развернём подстроку: 10001111.
Найдите лексикографически минимальную строку, которую можно получить из \(s\) после нуля или более преобразований.
Выходные данные
Для каждого примера на отдельной строке выведите лексикографически минимальную строку, которую можно получить из \(s\) после нуля или более преобразований.
Примечание
В первом примере достаточно применить одно преобразование ко всей строке целиком.
Во втором примере необходимо два преобразования: 0111001, 0110110.
В третьем примере строка в результате любого преобразования не меняется.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
100101
1100011
10101010
|
010110
0110110
10101010
|