طورت Infinite Compression Plan Consortium ‏(ICPC) استراتيجية جديدة رائعة لضغط البيانات، تسمى «Don’t Repeat Yourself» ‏(DRY). تعمل DRY على سلسلة محارف، وإذا احتوت السلسلة على ظهورين متتاليين للسلسلة الجزئية نفسها، فإنها تحذف أحدهما ببساطة. مثلًا، في «alfalfa seeds»، يمكنها حذف إحدى نسختي «e» في «seeds»، وإحدى نسختي «lfa» في «alfalfa»، لينتج «alfa seds». ويمكن لـ DRY أيضًا الاستفادة من عمليات الحذف السابقة؛ مثلًا، في «seventeenth baggage»، تحذف أولًا «e» المكررة في «seventeenth» و«g» المكررة في «baggage»، لينتج «sevententh bagage»، ثم تحذف «ent» المكررة في «sevententh» و«ag» المكررة في «bagage»، لينتج «seventh bage».

صورة مقتبسة بتعديل من Wikimedia Commons، ضمن الملكية العامة

إذا وُجدت عدة خيارات لسلاسل جزئية متكررة متتالية يمكن حذفها، فعلى DRY أن تختار بحيث تكون السلسلة النهائية أقصر ما يمكن. مثلًا، في «ABBCDCABCDCD»، هناك خياران: حذف «B» المكررة قرب البداية، أو «CD» المكررة في النهاية. إذا حُذفت «B»، يمكن بعد ذلك حذف «ABCDC» المكررة، لينتج «ABCDCD»، ثم حذف «CD» في النهاية أخيرًا، لينتج «ABCD». لكن إذا حُذفت «CD» في النهاية أولًا، فستبقى «ABBCDCABCD»، ولا يمكن حينئذ إلا حذف «B» المكررة للحصول على «ABCDCABCD»، ولا يمكن حذف شيء آخر من هذه السلسلة. لذا فالخيار الصحيح هو البدء بضغط «B» المزدوجة، والانتهاء بـ «ABCD».

لاحظت ICPC أن DRY تحقق أفضل النتائج على السلاسل الثنائية، أي السلاسل المكونة من الأصفار والآحاد فقط. لذلك كلفتك بتنفيذ أفضل خوارزمية DRY ممكنة تعمل على السلاسل الثنائية. لأي سلسلة ثنائية، عليك طباعة أقصر سلسلة يمكن الحصول عليها بتطبيق DRY عليها مرارًا.

الإدخال

يتكون الإدخال من سطر واحد يحتوي سلسلة غير فارغة طولها لا يتجاوز $10^5$، ومكونة من الأصفار والآحاد فقط.

الإخراج

اطبع سطرًا واحدًا يحتوي أقصر نتيجة ممكنة لتطبيق DRY على سلسلة الإدخال. إذا وُجدت عدة نتائج بأقصر طول، فستُقبل أي منها.

أمثلة

الإدخال 1

1111

الإخراج 1

1

الإدخال 2

101

الإخراج 2

101

الإدخال 3

10110

الإخراج 3

10