Backup System

Interview

Time limit2sMemory limit1024 MB

Summary

Simulate a backup system on a lowercase string: when a character repeats, output the suffix after its last occurrence as a backup, then print the final string.

Level: Medium4 of 10
Topics: Simulation, Stack, String
Solved: No attempts yet

Problem

British scientists have once again amazed the world with a new invention. This time they presented an innovative version of a backup system. Like all their inventions, it has one significant drawback: for now it can only be applied to strings made of lowercase Latin letters. But when has such a problem ever stopped anyone?

Your task is to implement this system. The idea is simple. The characters of a string are fed in one at a time. Whenever the system meets a character that already appears in the current version of the string, it finds the last occurrence of that character and erases everything written in the current version after that occurrence. Before erasing, the removed part is copied to a backup. Then the incoming character is appended to the current version. If the last occurrence is directly before the incoming character, nothing is erased and nothing is backed up.

The inventors claim that, given all the backed up strings and what remains in the current version, the original input string can be restored. You do not have to show how. Instead, for the input string, print everything that was erased and backed up, in the order it happened, followed by what remains in the current version.

Input

The input file contains one line with the string fed to the system, consisting of lowercase Latin letters. The length of the string does not exceed $200000$ characters.

Output

Each time a backup happens, print the backed up string on a new line. After the string ends, print the current version.

Examples1

Example 1
Input
```
abcabcdbcd
```
Expected output
```
bc
cd
aabbcd
```