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」入面，DRY 有兩個選擇：刪走近開頭重複嘅「B」，或者刪走結尾重複嘅「CD」。如果先刪「B」，DRY 跟住就可以刪走重複嘅「ABCDC」，得到「ABCDCD」，最後再刪走結尾嘅「CD」，得到「ABCD」。但係，如果 DRY 先刪走結尾嘅「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