압축

ICPC(Infinite Compression Plan Consortium)는 “Don’t Repeat Yourself”(DRY)라는 새로운 압축 기법을 개발했다. 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를 만든다.

지울 수 있는 연속 중복 부분 문자열이 여러 개라면, DRY는 최종 문자열이 가장 짧아지는 쪽을 고른다. 예를 들어 ABBCDCABCDCD에서는 앞쪽의 중복된 B를 지울 수도 있고, 뒤쪽의 중복된 CD를 지울 수도 있다. B를 먼저 지우면 중복된 ABCDC도 지울 수 있어 ABCDCD가 되고, 마지막으로 뒤의 CD를 지워 ABCD가 된다. 뒤의 CD를 먼저 지우면 ABBCDCABCD가 된다. 이 상태에서는 중복된 B만 지울 수 있고, 그 결과 ABCDCABCD가 되면 더 지울 것이 없다. 따라서 올바른 첫 단계는 중복된 B를 압축하는 것이다.

ICPC는 DRY가 0과 1로만 이루어진 이진 문자열에서 가장 잘 동작한다는 것을 확인했다. 이에 따라 이진 문자열에 대해 가장 좋은 DRY 알고리즘을 구현하려 한다. 임의의 이진 문자열에 DRY를 반복해서 적용하여 얻을 수 있는 가장 짧은 문자열을 출력하라.

입력은 한 줄로 주어지며, 길이가 $10^5$ 이하인 비어 있지 않은 문자열이다. 문자열은 0과 1로만 이루어져 있다.

DRY를 입력에 반복 적용하여 얻을 수 있는 가장 짧은 문자열을 한 줄에 출력하라. 가장 짧은 결과가 여러 개라면 그중 아무거나 출력해도 된다.