Infinite Compression Plan Consortium (ICPC) đã phát triển một chiến lược nén dữ liệu mới rất tốt, gọi là “Don’t Repeat Yourself” (DRY). DRY xử lý một xâu ký tự: nếu xâu chứa hai lần xuất hiện liên tiếp của cùng một xâu con, nó chỉ việc xóa một lần xuất hiện. Ví dụ, trong “alfalfa seeds”, nó có thể xóa một trong hai xâu con “e” trong “seeds”, và một trong hai xâu con “lfa” trong “alfalfa”, thu được “alfa seds”. DRY cũng có thể tận dụng các lần xóa trước đó: chẳng hạn, với “seventeenth baggage”, trước tiên nó xóa “e” lặp trong “seventeenth” và “g” lặp trong “baggage”, thu được “sevententh bagage”, rồi xóa “ent” lặp trong “sevententh” và “ag” lặp trong “bagage”, thu được “seventh bage”.

Hình ảnh được chỉnh từ Wikimedia Commons, thuộc phạm vi công cộng

Nếu có nhiều xâu con lặp liên tiếp có thể xóa, DRY phải chọn sao cho xâu cuối cùng ngắn nhất có thể. Ví dụ, với “ABBCDCABCDCD”, có hai lựa chọn: xóa “B” lặp gần đầu xâu, hoặc “CD” lặp ở cuối. Nếu xóa “B”, sau đó DRY có thể xóa “ABCDC” lặp, thu được “ABCDCD”, rồi cuối cùng xóa “CD” ở cuối để được “ABCD”. Tuy nhiên, nếu xóa “CD” ở cuối trước, sẽ còn “ABBCDCABCD”, từ đó chỉ có thể xóa “B” lặp để được “ABCDCABCD”, và xâu này không thể xóa thêm nữa. Vì vậy, lựa chọn đúng là bắt đầu bằng cách nén hai “B” và cuối cùng thu được “ABCD”.

ICPC nhận thấy DRY cho kết quả tốt nhất trên các xâu nhị phân, tức là xâu chỉ gồm các số không và một. Vì thế, họ giao cho bạn cài đặt thuật toán DRY tốt nhất có thể cho xâu nhị phân. Với mỗi xâu nhị phân bất kỳ, hãy in một xâu ngắn nhất có thể thu được bằng cách áp dụng DRY nhiều lần.

Dữ liệu vào

Đầu vào gồm một dòng chứa một xâu không rỗng có độ dài không quá $10^5$, chỉ gồm các số không và một.

Dữ liệu ra

In một dòng chứa một kết quả ngắn nhất có thể khi thực hiện DRY trên xâu đầu vào. Nếu có nhiều kết quả ngắn nhất, bất kỳ kết quả nào cũng được chấp nhận.

Ví dụ

Dữ liệu vào 1

1111

Dữ liệu ra 1

1

Dữ liệu vào 2

101

Dữ liệu ra 2

101

Dữ liệu vào 3

10110

Dữ liệu ra 3

10