Видаляємо підрядки

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

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

Вхідні дані

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

Вихідні дані

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

Приклади