Cipher

Interview

Time limit2sMemory limit1024 MB

Summary

Given a lowercase string of at most 1000 characters, print its lexicographically largest substring.

Level: Easy3 of 10
Topics: String
Solved: No attempts yet

Problem

Petya and Vasya like playing spies. No spy game goes without secret ciphers. Vasya recently invented a new way to encrypt his messages. He kept the encryption method secret and told Petya only the decryption method, so that Petya can always use it.

To decrypt, Petya must find the lexicographically largest substring of the encrypted message that Vasya sends him. That substring is the original text. Petya does not search fast enough, so he asks you to write a program that helps him.

Input

The first and only line contains a non-empty encrypted message made up only of lowercase Latin letters. The message is at most 1000 characters long.

Output

Print the decrypted message to the output file.

Examples2

Example 1
Input
```
abacaba
```
Expected output
```
caba
```
Example 2
Input
```
babb
```
Expected output
```
bb
```