CF1458D Flip and Reverse

给定一个只包含 $0$ 和 $1$ 的字符串 $s$。你可以进行如下操作： 1. 选择 $s$ 的一个非空连续子串，且该子串中 $0$ 和 $1$ 的数量相等； 2. 翻转该子串中的所有字符，即将所有 $0$ 变为 $1$，所有 $1$ 变为 $0$； 3. 反转该子串。 例如，考虑 $s = 00111011$，可以进行如下操作： - 选择前六个字符作为操作的子串：**001110**11。注意该子串中 $0$ 和 $1$ 的数量相等，因此是合法的选择。选择子串 0、110 或整个字符串都不是合法选择。 - 翻转该子串中的所有字符：**110001**11。 - 反转该子串：**100011**11。 请你求出经过若干次（可以为零次）上述操作后，能够得到的字典序最小的字符串。

第一行包含一个整数 $T$（$1 \leq T \leq 5 \cdot 10^5$），表示测试用例的数量。接下来的 $T$ 行，每行包含一个非空字符串，表示每个测试用例的输入字符串 $s$。 所有字符串均由字符 $0$ 和 $1$ 组成，且所有字符串的总长度不超过 $5 \cdot 10^5$。

对于每个测试用例，输出一行，表示经过若干次操作后能够得到的字典序最小的字符串。

在第一个测试用例中，应对整个字符串进行一次操作。 在第二个测试用例中，需要进行两次操作：**011100**1，011**0110**。 在第三个测试用例中，无论进行多少次操作，字符串都不会发生变化。 由 ChatGPT 4.1 翻译