310461: CF1837C. Best Binary String

C. Best Binary Stringtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are given a string $s$ consisting of the characters 0, 1 and/or ?. Let's call it a pattern.

Let's say that the binary string (a string where each character is either 0 or 1) matches the pattern if you can replace each character ? with 0 or 1 (for each character, the choice is independent) so that the strings become equal. For example, 0010 matches ?01?, but 010 doesn't match 1??, ??, or ????.

Let's define the cost of the binary string as the minimum number of operations of the form "reverse an arbitrary contiguous substring of the string" required to sort the string in non-descending order.

You have to find a binary string with the minimum possible cost among those that match the given pattern. If there are multiple answers, print any of them.

Input

The first line contains a single integer $t$ ($1 \le t \le 3 \cdot 10^4$) — the number of test cases.

The first and only line of each test case contains the string $s$ ($1 \le |s| \le 3 \cdot 10^5$) consisting of characters 0, 1, and/or ?.

The sum of the string lengths over all test cases does not exceed $3 \cdot 10^5$.

Output

For each test case, print a binary string with the minimum possible cost among those that match the given pattern. If there are multiple answers, print any of them.

ExampleInput

4
??01?
10100
1??10?
0?1?10?10

Output

00011
10100
111101
011110010

Note

In the first test case of the example, the cost of the resulting string is $0$.

In the second test case, the cost of the resulting string is $2$: we can reverse the substring from the $1$-st character to the $5$-th character, and we obtain the string 00101. Then we reverse the substring from the $3$-rd to the $4$-th character, and we obtain the string 00011, which is sorted in non-descending order.

题目大意：
C. 最佳二进制字符串

给定一个由字符0、1和/或?组成的字符串s，我们称之为模式。

如果一个二进制字符串（每个字符都是0或1的字符串）与模式匹配，那么你可以将每个字符?替换为0或1（每个字符的选择是独立的），使字符串相等。例如，0010与?01?匹配，但010不匹配1??、??或????。

定义二进制字符串的成本为将字符串按非降序排序所需的最小操作数，操作形式为“反转字符串的任意连续子串”。

你需要找出在匹配给定模式的二进制字符串中成本最小的字符串。如果有多个答案，则输出其中任意一个。

输入输出数据格式：

输入：
第一行包含一个整数t（1≤t≤3×10^4）——测试用例的数量。
每个测试用例的第一行且唯一一行包含一个由字符0、1和/或?组成的字符串s（1≤|s|≤3×10^5）。
所有测试用例的字符串长度之和不超过3×10^5。

输出：
对于每个测试用例，输出一个在匹配给定模式的二进制字符串中成本最小的字符串。如果有多个答案，则输出其中任意一个。

示例：

输入：
4
??01?
10100
1??10?
0?1?10?10

输出：
00011
10100
111101
011110010

注意：
在示例的第一个测试用例中，结果字符串的成本为0。
在第二个测试用例中，结果字符串的成本为2：我们可以反转从第1个字符到第5个字符的子串，得到字符串00101。然后我们反转从第3个到第4个字符的子串，得到字符串00011，它按非降序排序。题目大意： C. 最佳二进制字符串 给定一个由字符0、1和/或?组成的字符串s，我们称之为模式。 如果一个二进制字符串（每个字符都是0或1的字符串）与模式匹配，那么你可以将每个字符?替换为0或1（每个字符的选择是独立的），使字符串相等。例如，0010与?01?匹配，但010不匹配1??、??或????。 定义二进制字符串的成本为将字符串按非降序排序所需的最小操作数，操作形式为“反转字符串的任意连续子串”。 你需要找出在匹配给定模式的二进制字符串中成本最小的字符串。如果有多个答案，则输出其中任意一个。 输入输出数据格式： 输入： 第一行包含一个整数t（1≤t≤3×10^4）——测试用例的数量。 每个测试用例的第一行且唯一一行包含一个由字符0、1和/或?组成的字符串s（1≤|s|≤3×10^5）。 所有测试用例的字符串长度之和不超过3×10^5。 输出： 对于每个测试用例，输出一个在匹配给定模式的二进制字符串中成本最小的字符串。如果有多个答案，则输出其中任意一个。 示例： 输入： 4 ??01? 10100 1??10? 0?1?10?10 输出： 00011 10100 111101 011110010 注意： 在示例的第一个测试用例中，结果字符串的成本为0。 在第二个测试用例中，结果字符串的成本为2：我们可以反转从第1个字符到第5个字符的子串，得到字符串00101。然后我们反转从第3个到第4个字符的子串，得到字符串00011，它按非降序排序。