← 返回题目列表

Codeforces · 1837/C

C. 最佳二进制字符串

中文机器翻译题面 查看原题

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

假设二进制字符串(每个字符为 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$$$。

输出

对于每个测试用例,打印与给定模式匹配的最小可能成本的二进制字符串。如果有多个答案,请打印其中任何一个。

示例

输入 #1

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

输出 #1

00011
10100
111101
011110010

注意

在示例的第一个测试用例中,结果字符串的成本为 $$$0$$$。

在第二个测试用例中,结果字符串的成本为$$$2$$$:我们可以将子字符串从$$$1$$$-st字符反转到第$$$5$$$字符,得到字符串00101。然后我们将子字符串从$$$3$$$-rd反转到第$$$4$$$字符,得到字符串00011,按非降序排序。