Suffix Game (Hard)

Ksusha is playing a game involving strings.

In this game, Ksusha writes letters sequentially on a sheet of paper. On the first step, she writes the letter (s_1), on the second step (s_2), and so forth. She also has a string (t), which is used to calculate her score in the game.

The scoring works as follows: On the first step, the number of times the string (s_1) appears in (t) is added to her score. On the second step, the number of times the string (s_1s_2) appears in (t) is added. On the third step, the number of times (s_1s_2s_3) appears in (t) is added, and so on. Initially, her score is (0).

Ksusha can stop writing letters whenever she chooses. Your task is to help her devise a strategy that maximizes her score. In other words, determine the string (s_1s_2...s_n) that, when written by Ksusha, yields the highest possible score.

Input

The first line contains the string (t) ((1 $\le$ |t| $\le$ 10^5)). The string (t) consists solely of lowercase Latin letters.

Output

Output the solution to the problem — the string (s). If there are multiple strings that yield the maximum score, output the lexicographically smallest one.

Examples