C. Лучшая двоичная строка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана строка $$$s$$$, состоящая из символов 0, 1 и/или ?. Назовем эту строку шаблоном.

Скажем, что двоичная строка (строка, где каждый символ равен либо 0, либо 1) соответствует шаблону, если возможно заменить каждый символ ? на 0 или 1 (для каждого символа выбор независим) так, чтобы строки стали равны. Например, 0010 соответствует ?01?, но 010 не соответствует ни 1??, ни ??, ни ????.

Давайте определим стоимость двоичной строки как минимальное количество операций вида «перевернуть произвольную непрерывную подстроку строки», необходимых, чтобы строка оказалась отсортированной в порядке неубывания.

Ваша задача — найти двоичную строку с минимально возможной стоимостью среди тех, которые соответствуют заданному шаблону. Если ответов несколько, выведите любой из них.

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 3 \cdot 10^4$$$) — количество наборов входных данных.

Первая и единственная строка каждого набора содержит строку $$$s$$$ ($$$1 \le |s| \le 3 \cdot 10^5$$$), состоящую из символов 0, 1 и/или ?.

Сумма длин строк по всем наборам входных данных не превосходит $$$3 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите двоичную строку с минимально возможной стоимостью среди тех, которые соответствуют заданному шаблону. Если ответов несколько, выведите любой из них.

Пример
Входные данные
4
??01?
10100
1??10?
0?1?10?10
Выходные данные
00011
10100
111101
011110010
Примечание

В первом наборе входных данных в примере из условия стоимость полученной строки равна $$$0$$$.

Во втором наборе входных данных стоимость полученной строки равна $$$2$$$: мы можем перевернуть подстроку с $$$1$$$-го символа по $$$5$$$-й, и мы получим строку 00101. Затем мы можем перевернуть подстроку с $$$3$$$-го по $$$4$$$-й символ, и мы получим строку 00011, которая отсортирована в порядке неубывания.