Вам дана строка \(s\) из символов 0 и 1. Вы можете делать преобразование следующего вида:
Например, рассмотрим \(s\) = 00111011, и следующее преобразование:
Найдите лексикографически минимальную строку, которую можно получить из \(s\) после нуля или более преобразований.
В первой строке записано одно целое число \(T\) (\(1 \leq T \leq 5 \cdot 10^5\)) — количество тестовых примеров. Каждая из следующих \(T\) строк содержит одну непустую последовательность символов — строку \(s\) в соответствующем примере.
Все строки состоят из символов 0 и 1, и их суммарная длина не превосходит \(5 \cdot 10^5\).
Для каждого примера на отдельной строке выведите лексикографически минимальную строку, которую можно получить из \(s\) после нуля или более преобразований.
В первом примере достаточно применить одно преобразование ко всей строке целиком.
Во втором примере необходимо два преобразования: 0111001, 0110110.
В третьем примере строка в результате любого преобразования не меняется.
3 100101 1100011 10101010
010110 0110110 10101010
2000 ms 512 Mb Правила оформления программ и список ошибок при автоматической проверке задач