Problem

In Popland, music has become incredibly repetitive in order to be as catchy as possible. Every song is just a short melody repeated over and over again. As a result, after hearing only a short segment of a song, it is possible to figure out the next notes and start humming along.

While visiting Popland, you turn on the radio and catch a few notes of the song playing. You are sure that you heard the song’s underlying melody in it’s entirety at least twice. Can you figure out what the next five notes will be?

Input

A test case contains a string of the uppercase letters, representing the notes that you heard.

For the first $40%$ of cases, the length of the string will be less than $1000$.

For the remaining $60%$ of cases, the length of the string will be less than $10^6$.

Output

Output a string containing the next five notes of the song.

Sample Input 1

ABCABCABCAB

Sample Output 1

CABCA

Sample Input 2

ABAACABAACA

Sample Output 2

BAACA

Sample Input 3

NDCATSANDBOOTSANDCATSANDBOOTSANDCATSAND

Sample Output 3

BOOTS

Editorial

Read only if you are stuck or have already solved the problem.