D. Флипы и развороты
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана строка $$$s$$$ из символов 0 и 1. Вы можете делать преобразование следующего вида:

  • выбрать непустую сплошную подстроку $$$s$$$, содержащую одинаковое количество символов 0 и 1;
  • заменить все символы 0 в подстроке на 1, и наоборот;
  • развернуть подстроку.

Например, рассмотрим $$$s$$$ = 00111011, и следующее преобразование:

  • Выберем в качестве подстроки первые шесть символов: 00111011. Эту подстроку можно выбрать, поскольку в ней количество 0 и 1 совпадает. Выбирать подстроки 0, 110, или всю строку целиком нельзя.
  • Заменим все символы в подстроке на противоположные: 11000111.
  • Развернём подстроку: 10001111.

Найдите лексикографически минимальную строку, которую можно получить из $$$s$$$ после нуля или более преобразований.

Входные данные

В первой строке записано одно целое число $$$T$$$ ($$$1 \leq T \leq 5 \cdot 10^5$$$) — количество тестовых примеров. Каждая из следующих $$$T$$$ строк содержит одну непустую последовательность символов — строку $$$s$$$ в соответствующем примере.

Все строки состоят из символов 0 и 1, и их суммарная длина не превосходит $$$5 \cdot 10^5$$$.

Выходные данные

Для каждого примера на отдельной строке выведите лексикографически минимальную строку, которую можно получить из $$$s$$$ после нуля или более преобразований.

Пример
Входные данные
3
100101
1100011
10101010
Выходные данные
010110
0110110
10101010
Примечание

В первом примере достаточно применить одно преобразование ко всей строке целиком.

Во втором примере необходимо два преобразования: 0111001, 0110110.

В третьем примере строка в результате любого преобразования не меняется.