Infinite Compression Plan Consortium（ICPC）は、「Don’t Repeat Yourself」（DRY）という優れた新しいデータ圧縮方式を開発しました。DRY は文字列に作用し、同じ部分文字列が二つ連続して現れたら、その一方を削除するだけです。例えば「alfalfa seeds」では、「seeds」の二つの「e」の一方と、「alfalfa」の二つの「lfa」の一方を削除して、「alfa seds」にできます。DRY は以前の削除を活用することもできます。例えば「seventeenth baggage」では、まず「seventeenth」の重複する「e」と「baggage」の重複する「g」を削除して「sevententh bagage」にし、次に「sevententh」の重複する「ent」と「bagage」の重複する「ag」を削除して「seventh bage」にします。

Wikimedia Commons の画像を改変、パブリックドメイン

削除できる連続した重複部分文字列が複数ある場合、DRY は最終的な文字列ができるだけ短くなるように選ぶ必要があります。例えば「ABBCDCABCDCD」では、先頭近くの重複する「B」を削除するか、末尾の重複する「CD」を削除するかの二つの選択肢があります。「B」を削除すると、次に重複する「ABCDC」を削除して「ABCDCD」にでき、最後に末尾の「CD」を削除して「ABCD」にできます。一方、先に末尾の「CD」を削除すると「ABBCDCABCD」が残り、そこからは重複する「B」を削除して「ABCDCABCD」にすることしかできず、それ以上何も削除できません。したがって DRY の正しい選択は、最初に二重の「B」を圧縮し、最終的に「ABCD」を得ることです。

ICPC は、DRY が二進文字列、すなわちゼロと一だけからなる文字列で最もよい結果を得ることに気づきました。そこで、二進文字列に対して最善の結果を得る DRY アルゴリズムの実装をあなたに依頼しました。任意の二進文字列について、DRY を繰り返し適用して得られる最短の文字列を出力してください。

入力

入力は一行からなり、ゼロと一のみからなる長さ $10^5$ 以下の空でない文字列を含みます。

出力

入力文字列に DRY を適用して得られる最短の結果を一行で出力してください。最短の結果が複数ある場合は、どれを出力してもかまいません。

入出力例

入力 1

1111

出力 1

1

入力 2

101

出力 2

101

入力 3

10110

出力 3

10