Infinite Compression Plan Consortium (ICPC) telah mengembangkan strategi kompresi data baru yang hebat, bernama “Don’t Repeat Yourself” (DRY). DRY bekerja pada string karakter: jika string memuat dua kemunculan berurutan dari substring yang sama, salah satunya dihapus. Misalnya, pada “alfalfa seeds”, DRY dapat menghapus satu dari dua substring “e” pada “seeds” dan satu dari dua substring “lfa” pada “alfalfa”, sehingga diperoleh “alfa seds”. DRY juga dapat memanfaatkan penghapusan sebelumnya: pada “seventeenth baggage”, misalnya, mula-mula dihapus “e” yang berulang pada “seventeenth” dan “g” yang berulang pada “baggage”, menghasilkan “sevententh bagage”, lalu “ent” yang berulang pada “sevententh” dan “ag” yang berulang pada “bagage”, menghasilkan “seventh bage”.
Gambar diadaptasi dari Wikimedia Commons, domain publik
Jika ada beberapa pilihan substring berulang yang berurutan untuk dihapus, DRY harus memilih agar string akhir menjadi sependek mungkin. Misalnya, pada “ABBCDCABCDCD”, terdapat dua pilihan: menghapus “B” berulang di dekat awal, atau “CD” berulang di akhir. Jika “B” dihapus, DRY kemudian dapat menghapus “ABCDC” berulang, menghasilkan “ABCDCD”, lalu akhirnya menghapus “CD” di akhir untuk memperoleh “ABCD”. Namun, jika “CD” di akhir dihapus terlebih dahulu, akan tersisa “ABBCDCABCD”, yang hanya dapat dihapus “B” berulangnya untuk menjadi “ABCDCABCD”, dan tidak ada lagi yang dapat dihapus dari string itu. Jadi, pilihan yang benar adalah mulai dengan mengompresi “B” ganda dan akhirnya menghasilkan “ABCD”.
ICPC mengamati bahwa DRY memberikan hasil terbaik pada string biner, yaitu string yang hanya terdiri atas nol dan satu. Karena itu, Anda ditugaskan mengimplementasikan algoritma DRY terbaik untuk string biner. Untuk sembarang string biner, keluarkan string terpendek yang dapat diperoleh dengan menerapkan DRY berulang kali.
Masukan
Masukan terdiri atas satu baris berisi string tidak kosong dengan panjang paling banyak $10^5$, yang hanya terdiri atas nol dan satu.
Keluaran
Keluarkan satu baris berisi hasil terpendek yang mungkin dari penerapan DRY pada string masukan. Jika ada beberapa hasil terpendek, hasil mana pun akan diterima.
Contoh
Masukan 1
1111
Keluaran 1
1
Masukan 2
101
Keluaran 2
101
Masukan 3
10110
Keluaran 3
10