Наряду с непростой судьбой у Надэко есть строка $s$, состоящая из строчных букв. Её заветное желание — построить строку $t$, для которой выполняются следующие условия:
- $t$ не содержит $s$ в качестве подпоследовательности.
- Каждая подпоследовательность строки $s$, не совпадающая с $s$, содержится в $t$ в качестве подпоследовательности.
Помогите ей найти строку $t$ минимально возможной длины. Если таких строк несколько, разрешается вывести любую из них.
Входные данные
Единственная строка входных данных содержит строку $s$ ($2 \le |s| \le 10^6$) — строку Надэко. Гарантируется, что $s$ состоит только из строчных букв.
Выходные данные
В единственной строке выведите любую строку $t$ минимальной длины, удовлетворяющую условиям задачи.
Примеры
Входные данные 1
aaaa
Выходные данные 1
aaa
Входные данные 2
bba
Выходные данные 2
bab
Примечание
Во втором примере строка bab содержит bb, ba, a, b в качестве подпоследовательностей, но не содержит bba. Также очевидно, что невозможно построить корректную последовательность длины $2$, поэтому bab является возможным ответом.