JDCC '16 Contest 1 P5 - Catchy Music

View as PDF
Submit solution
Points: 12 (partial)
Time limit: 2.0s
Memory limit: 128M
Author:
rtilikay
Problem type

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 its 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 1 000.

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

ABCABCABCAB

Sample Output

CABCA

Sample Input

ABAACABAACA

Sample Output

BAACA

Sample Input

NDCATSANDBOOTSANDCATSANDBOOTSANDCATSAND

Sample Output

BOOTS

Comments


  • 1
    MstrPikachu  commented on Nov. 9, 2018, 4:37 p.m.

    You used the wrong "its"


    • 1
      Ninjaclasher  commented on Nov. 9, 2018, 4:38 p.m.

      Fixed. Thank you for pointing that out.


      • 1
        ssheep  commented on Nov. 13, 2018, 12:07 p.m. ← edited

        no u - larry


        • 1
          _  commented on Nov. 24, 2018, 7:59 p.m.

          no u