题目描述

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

如果一个二进制字符串（即每个字符都是 $0$ 或 $1$）可以通过将模式串中的每个 $?$ 独立替换为 $0$ 或 $1$，使得两个字符串完全相同，则称该二进制字符串与该模式串匹配。例如，$0010$ 匹配 $?01?$，但 $010$ 不匹配 $1??$、$??$ 或 $????$。

我们定义一个二进制字符串的代价为：将该字符串通过若干次“翻转任意连续子串”操作，使其变为非递减顺序（即所有 $0$ 在前，所有 $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$。

输出格式

对于每个测试用例，输出一个与给定模式串匹配且代价最小的二进制字符串。如果有多个答案，输出任意一个即可。

说明/提示

在示例的第一个测试用例中，输出字符串的代价为 $0$。

在第二个测试用例中，输出字符串的代价为 $2$：我们可以先翻转第 $1$ 个到第 $5$ 个字符的子串，得到 $00101$。然后再翻转第 $3$ 个到第 $4$ 个字符的子串，得到 $00011$，此时字符串已按非递减顺序排列。

由 ChatGPT 4.1 翻译

样例

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

00011
10100
111101
011110010