Removing substrings

Given a string s consisting of n lowercase Latin letters, you need to perform k operations on it, where k = ⌊log[2](n)⌋. In the i-th operation, you must remove a substring of length exactly 2^(i-1) from s.

Your task is to output the lexicographically smallest string possible after completing all the operations.

Input

The input consists of a single line containing the string s, which has n lowercase Latin characters (1 ≤ n ≤ 5000).

Output

Print the lexicographically smallest string that can be obtained after performing all k operations.

Examples