백업 시스템

천재적인 영국 과학자들이 또다시 새로운 발명품으로 세상을 놀라게 했다. 이번에는 백업 시스템의 혁신적인 버전을 선보였다. 그러나 그들의 다른 발명품과 마찬가지로 큰 단점이 하나 있다. 지금은 소문자 라틴 알파벳으로 이루어진 문자열에만 적용할 수 있다는 것이다. 하지만 이런 문제로 발목이 잡혔던 사람이 언제 있었던가?

여러분은 이 시스템을 구현해야 한다. 원리는 단순하다. 문자열의 문자가 한 번에 하나씩 입력으로 들어온다. 시스템은 현재 버전의 문자열에 이미 있는 문자를 만나면, 그 문자의 마지막 출현 위치를 찾아 그 뒤에 현재 버전에 적혀 있던 내용을 모두 지운다. 지우기 전에 지워진 부분은 백업된다. 그다음 들어온 문자를 현재 버전 끝에 덧붙인다. 마지막 출현 위치가 들어온 문자의 바로 앞이라면, 아무것도 지우지 않으며 백업도 하지 않는다.

발명자들은 백업된 모든 문자열과 현재 버전에 남은 문자열이 있으면 원래 입력 문자열을 복원할 수 있다고 주장한다. 복원 방법을 보일 필요는 없다. 대신 입력 문자열에 대해, 지워져서 백업된 내용을 일어난 순서대로 모두 출력하고, 마지막으로 현재 버전에 남은 문자열을 출력하라.

입력 파일에는 시스템에 주어지는 소문자 라틴 알파벳으로 이루어진 문자열이 한 줄 들어 있다. 문자열의 길이는 $200000$을 넘지 않는다.

백업이 일어날 때마다 백업된 내용을 새 줄에 출력한다. 문자열이 끝나면 현재 버전을 출력한다.