Дано рядок s, який з самого початку складається з n малих латинських літер. Над ним виконують k операції, де k=⌊log2(n)⌋. Під час i-тої операції необхідно видалити деякий підрядок розміром довжиною рівно 2i-1 з рядка s.

Виведіть лексикографічно мінімальний рядок, який можна отримати після виконання всіх операцій.

Вхідні дані:

Єдиний рядок містить один рядок s з n малих латинських символів (**1 ≤ n ≤ 5000**).

Вихідні дані:

Виведіть лексикографічно мінімальний рядок, який можна отримати після виконання k операцій.