Шифровка

Петя и Вася любят играть в шпионов. А какие игры в шпионов обходятся без секретных шифровок! Вот и Вася недавно придумал новый способ шифрования своих сообщений. Информацию о том, как он шифрует, он оставил в секрете и сообщил Пете только способ расшифровки, чтобы тот всегда мог им воспользоваться.

Для расшифровки Пете необходимо всего лишь найти лексикографически максимальную подстроку в зашифрованном сообщении, которое ему передает Вася. Именно эта подстрока и будет исходным текстом. Поскольку Петя справляется с этим поиском не так быстро, как ему хотелось бы, он просит Вас написать программу, которая поможет ему в этом!

Первая и единственная строка входного файла содержит непустое зашифрованное сообщение, состоящее только из строчных букв латинского алфавита. Сообщение имеет длину не более $1000$ символов.

В выходной файл выведите расшифрованное сообщение.