Wipe it!

Interview

Time limit2sMemory limit1024 MB

Summary

Simulate a teacher writing a word one letter at a time, wiping each suffix that already appears elsewhere in the word, and output the final word on the board.

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

Statement

A computer science teacher made an exercise to make his lessons more entertaining. During the exercise the teacher writes the letters of a word he has thought of on the blackboard, one at a time, in order. The students must shout <<Wipe it!>> each time the word on the blackboard has a suffix that has already occurred at some other location in the word.

When the teacher hears the shout, he wipes off the suffix the students found and continues writing the remaining letters.

Assuming the students complete their task perfectly, find the word that is on the blackboard at the end of the exercise.

Input

The input is a single line containing the word the teacher thought of. It consists of lowercase English letters, and its length does not exceed $1000$ .

Output

Output a single line containing the word on the blackboard at the end of the exercise.

Examples2

Example 1
Input
```
abcabc
```
Expected output
```
abc
```
Example 2
Input
```
aaaaaaaa
```
Expected output
```
a
```