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