#8227. 「codeforce」最小三元字符串 普及/提高−

时间限制:1000 ms 内存限制:128 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: shaobai

题目描述

给你一个三元字符串(这是一个只由字符 "0"、"1 "和 "2 "组成的字符串)。

您可以交换任意两个相邻(连续)的字符 "0 "和 "1"(即用 "10 "替换 "01",反之亦然),或任意两个相邻(连续)的字符 "1 "和 "2"(即用 "21 "替换 "12",反之亦然)。

例如,对于字符串 "010210",我们可以执行以下操作:

  • "010210" "100210";
  • "010210" "001210";
  • "010210" "010120";
  • "010210" "010201".

注意不能将 "02" 与 "20 "对调,反之亦然。"20",反之亦然。除上述操作外,您不能对给定字符串执行任何其他操作。

您的任务是通过任意次数(可能为零)的交换,获得尽可能小的(按词法)字符串。

如果存在某个位置 ,其中 是字符串 的长度),使得每个 都持有 ,那么字符串 在词法上小于字符串 (如果字符串 的长度相同)。

输入格式

输入

输入的第一行包含仅由字符 "0"、"1 "和 "2 "组成的字符串 ,其长度在 (含)之间。

输出格式

输出

打印一个字符串--通过使用上述任意次数(可能为零)的交换,可以获得的最小字符串(按词法)。

样例

样例输入

100210

样例输出

001120