题目描述

小 Y 开发了一种名为“别重复”的新型数据压缩策略。“别重复”作用于字符串，若字符串中存在两个连续相同的子串，则会删除其中一个。例如，在字符串 $\tt alfalfaseeds$ 中，“别重复”可删除 $\tt seeds$ 中的一个 $\tt e$和 $\tt alfalfa$ 中的一个 $\tt lfa$，得到 $\tt alfaseds$。 “别重复”还能利用先前的删除效果，例如在 $\tt seventeenth\ baggage$ 中，先删除重复的 $\tt e$ 和 $\tt g$ 得到 $\tt sevententh\ bagage$，再删除重复的 $\tt ent$ 和 $\tt ag$，最终得到 $\tt seventh\ bage$。

当存在多个重复子串可删除时，最优的“别重复”会选择使最终字符串最短的方式。例如，在 $\tt ABBCDCABCDCD$ 中，优先删除开头的 $\tt B$ 再删除 $\tt ABCDC$ 可压缩为 $\tt ABCD$，而若先删除末尾的 $\tt CD$ 再删除 $\tt B$ 则最终只能得到 $\tt ABCDCABCD$。最优的“别重复”会选择先删除 $\tt B$ 再删除 $\tt ABCDC$ 的方式。

小 Y 要求为带通配符的二进制字符串（仅含 $\tt 0,1,\#$，$\tt\#$ 为通配符）实现最优的“别重复”算法。你需要在进行“别重复”压缩算法前为通配符进行赋值，值为 $\tt 0$ 或者 $\tt 1$，使得赋值之后的二进制字符串通过应用最优的“别重复”能得到最短的字符串。

输入格式

一行一个带通配符的二进制字符串。

输出格式

一行一个字符串表示应用最优的“别重复”能得到的最短字符串。数据保证应用最优的“别重复”能得到的最短字符串有且只有一种唯一情况。

111#

1

10#

10

10##1

101

数据范围

本任务共有 $10$ 个数据。

对于全部数据：保证字符串长度不超过 $10^5$，数据保证应用最优的“别重复”能得到的最短字符串有且只有一种唯一情况。