给你一个三元字符串(它是一个仅由字符“0”、“1”和“2”组成的字符串)。
您可以交换任意两个相邻(连续)字符“0”和“1”(即将“01”替换为“10”,反之亦然)或任意两个相邻(连续)字符“1”和“2”(即将“12”替换为“21”,反之亦然)。
例如,对于字符串“010210”,我们可以执行以下操作:
- "010210" $$$\rightarrow$$$ "100210";
- "010210" $$$\rightarrow$$$ "001210";
- "010210" $$$\rightarrow$$$ "010120";
- “010210”$$$\rightarrow$$$“010201”。
请注意,您不能交换“02”$$$\rightarrow$$$“20”,反之亦然。除了上述之外,您不能对给定字符串执行任何其他操作。
您的任务是通过使用这些交换任意次数(可能为零)来获取最小可能(按字典顺序)的字符串。
如果存在某个位置 $$$i$$$($$$1 \le i \le |a|$$$,其中 $$$|s|$$$ 是字符串 $$$s$$$ 的长度),则字符串 $$$a$$$ 按字典顺序小于字符串 $$$b$$$(如果字符串 $$$a$$$ 和 $$$b$$$ 具有相同的长度),这样对于每个$$$j < i$$$ 成立 $$$a_j = b_j$$$,且 $$$a_i < b_i$$$。
输入
输入的第一行包含字符串 $$$s$$$,仅由字符 '0'、'1' 和 '2' 组成,其长度在 $$$1$$$ 和 $$$10^5$$$ 之间(含)。
输出
打印单个字符串 - 通过使用上述交换任意次数(可能为零)可以获得的最小可能(按字典顺序)字符串。
示例
输入 #1
100210
输出 #1
001120
输入 #2
11222121
输出 #2
11112222
输入 #3
20
输出 #3
20