小Y开发了一种名为“别重复”的新型数据压缩策略。“别重复”作用于字符串，若字符串中存在两个连续相同的子串，则会删除其中一个。例如，在字符串“alfalfaseeds”中，“别重复”可删除“seeds”中的一个“e”和“alfalfa”中的一个“lfa”，得到“alfaseds”。 “别重复”还能利用先前的删除效果，例如在“seventeenth
baggage”中，先删除重复的“e”和“g”得到“sevententh bagage”，再删除重复的“ent”和“ag”，最终得到“seventh bage”。
当存在多个重复子串可删除时，最优的“别重复”会选择使最终字符串最短的方式。例如，在“ABBCDCABCDCD”中，优先删除开头的“B”再删除“ABCDC”可压缩为“ABCD”，而若先删除末尾的“CD”再删除“B”则最终只能得到“ABCDCABCD”。最优的“别重复”会选择先删除“B”再删除“ABCDC”的方式。
小Y要求为带通配符的二进制字符串（仅含‘0’,‘1’,‘#’（通配符））实现最优的“别重复”算法。你需要在进行“别重复”压缩算法前为通配符进行赋值，值为‘0’或者‘1’，使得赋值之后的二进制字符串通过应用最优的“别重复”能得到最短的字符串。
一行一个带通配符的二进制字符串。
一行一个字符串表示应用最优的“别重复”能得到的最短字符串。题目数据保证应用最优的“别重复”能得到的最短字符串有且只有一种唯一情况。
样例输入1
111#
样例输入2
10#
样例输入3
10##1样例输出1
1
样例输出2
10
样例输出3
101
数据范围
本题共有10个测试点，每个测试点10分。
对于全部测试点：保证字符串长度不超过100000，数据保证应用最优的“别重复”能得到的最短字符串有且只有一种唯一情况。
对于测试点1-2：1<=n<=3。n表示字符串长度
对于测试点3-4：1<=n<=100000,
字符串中不包含“0”。
对于测试点5-8：1<=n<=100000,
字符串中不包含“#”。