Дана строка \(s\), состоящая из символов 0, 1 и/или ?. Назовем эту строку шаблоном.
Скажем, что двоичная строка (строка, где каждый символ равен либо 0, либо 1) соответствует шаблону, если возможно заменить каждый символ ? на 0 или 1 (для каждого символа выбор независим) так, чтобы строки стали равны. Например, 0010 соответствует ?01?, но 010 не соответствует ни 1??, ни ??, ни ????.
Давайте определим стоимость двоичной строки как минимальное количество операций вида «перевернуть произвольную непрерывную подстроку строки», необходимых, чтобы строка оказалась отсортированной в порядке неубывания.
Ваша задача — найти двоичную строку с минимально возможной стоимостью среди тех, которые соответствуют заданному шаблону. Если ответов несколько, выведите любой из них.
Выходные данные
Для каждого набора входных данных выведите двоичную строку с минимально возможной стоимостью среди тех, которые соответствуют заданному шаблону. Если ответов несколько, выведите любой из них.
Примечание
В первом наборе входных данных в примере из условия стоимость полученной строки равна \(0\).
Во втором наборе входных данных стоимость полученной строки равна \(2\): мы можем перевернуть подстроку с \(1\)-го символа по \(5\)-й, и мы получим строку 00101. Затем мы можем перевернуть подстроку с \(3\)-го по \(4\)-й символ, и мы получим строку 00011, которая отсортирована в порядке неубывания.