← 返回题目列表

Codeforces · 1458/D

D. 翻转和反转

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

给你一个由 0 和 1 组成的字符串 $$$s$$$。您可以执行以下操作:

- 选择 $$$s$$$ 中包含相同数量的 0 和 1 的非空连续子字符串;
- 翻转子字符串中的所有字符,即将所有 0 替换为 1,反之亦然;
- 反转子字符串。

例如,考虑 $$$s$$$ = 00111011,以及以下操作:

- 选择前六个字符作为要操作的子字符串:00111011。请注意,0 和 1 的数量相等,因此这是合法的选择。选择子字符串 0、110 或整个字符串是不可能的。
- 翻转子字符串中的所有字符:11000111。
- 反转子字符串:10001111。

查找在零次或多次操作后可以从 $$$s$$$ 获得的按字典顺序最小的字符串。

输入

第一行包含一个整数 $$$T$$$ ($$$1 \leq T \leq 5 \cdot 10^5$$$) — 测试用例的数量。以下每行 $$$T$$$ 都包含一个非空字符串 - 相应测试用例的输入字符串 $$$s$$$。

所有字符串均由字符0和1组成,其总长度不超过$$$5 \cdot 10^5$$$。

输出

对于每个测试用例,在单独的行上打印在零次或多次操作后可以从 $$$s$$$ 获得的按字典顺序排列的最小字符串。

示例

输入 #1

3
100101
1100011
10101010

输出 #1

010110
0110110
10101010

注意

在第一个测试用例中,应将单个操作应用于整个字符串。

在第二个测试用例中需要两次操作:0111001、0110110。

在第三个测试用例中,字符串在任何操作后都保持不变。