Резервное копирование

Гениальные британские ученые в очередной раз потрясли мир новым великим изобретением. На этот раз они представили инновационную версию системы резервного копирования. Правда, как и у всех их изобретений, у нее есть один существенный недостаток. Этот недостаток заключается в том, что пока что она может быть реализована лишь для строк, состоящих из строчных символов латинского алфавита. Но когда и кого такие проблемы останавливали?

Перед вами поставлена задача реализовать эту систему. Суть системы достаточно проста. На вход подается по одному символу строки. Как только система встречает символ, который уже есть в текущей версии строки, она ищет его последнее вхождение и стирает (ну, естественно, не просто так стирает, а резервно копирует) все, что было записано в текущей версии строки после этого последнего вхождения. После чего поступивший символ дописывается к текущей версии. Естественно, что если последнее вхождение было непосредственно перед тем, как поступил текущий символ, то ничего не стирается и резервно не копируется.

Утверждается, что после всех этих действий, имея все резервно скопированные строки и то, что в итоге осталось в текущей версии, можно восстановить строку, которая подавалась на вход. Но мы не спрашиваем вас, как это сделать, а просим, наоборот, по строке, которая подается системе на вход, вывести все, что было из нее удалено и скопировано в том порядке, в котором это было сделано, а также вывести то, что в итоге осталось в текущей версии.

Во входном файле содержится одна строка, состоящая из строчных латинских символов --- то, что системе подается на вход. Длина строки не превышает $200000$ символов.

Каждый раз, когда происходит резервное копирование, выведите в новой строке то, что было резервно скопировано. После того, как строка закончилась, выведите текущую версию.