Suffix Game

Ksusha is playing a game with strings.

In this game, Ksusha writes letters on a sheet one at a time, in sequence. On the first step, she writes the letter (s_1), on the second step, she writes (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, results in the highest possible score.

Input

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

Output

Print the solution to the problem — the string (s). If multiple strings yield the same maximum score, print the lexicographically smallest one.

Note: A string (x = x_1x_2...x_p) is lexicographically smaller than a string (y = y_1y_2...y_q) if either (p < q) and (x_1 = y_1), (x_2 = y_2), ..., (x_p = y_p), or there exists a number (r) ((r < p), (r < q)), such that (x_1 = y_1), (x_2 = y_2), ..., (x_r = y_r) and (x_r+1 < y_r+1). The characters of the strings are compared by their ASCII codes.

Examples