E.太陽精靈的項練

題目敘述

在大家的一陣嘻笑聲中，一個不小心，水精靈的水柱噴濺到十分愛乾淨的太陽精靈身上，把太陽精靈一條很寶貝的項鍊弄髒了。伊布們嚇死了！趕緊衝衝上前賠罪，並幫他把項鍊給擦拭乾淨。

在他們忙著打理太陽精靈的同時，皮卡丘發現一件有趣的事，這條項鍊似乎是由同一種圖騰重複拼接起來而形成的，我們把每一種圖示用一個符號代替，那這條項鍊可以表示成$ABBABBABBABB$，那可以發現項鍊可以由圖騰$ABBABB$或$ABB$組成，因為太陽精靈是完美主義者，不能有一個圖騰因項鍊長度不夠而被截斷，這樣太不完美了！此時太陽精靈走了過來，告訴皮卡丘說可以組成項鍊的圖騰很多種，但其實只有最短的那個才是真正的圖騰，因為那才最精簡的美阿！

之後太陽精靈帶來了好幾條項鍊，說如果皮卡丘如果可以分辨項鍊上的圖騰是什麼的話，那它可以把這些條項鍊送給皮卡丘作為初次見面的禮物。你能幫皮卡丘分辨圖騰嗎？或許他會送其中你一條漂亮的項鍊的！

輸入說明

有多筆輸入，每筆輸入佔1行。
每行有一串字代表項鍊的樣子，項鍊的每個圖示都會用一個大寫字母來表示。

保證在所有狀況下項鍊的長度$L$滿足$0< L\leq 5*10^7$

輸出說明

對於每筆輸入都輸出一行，為該項鍊的圖騰樣式。

範例輸入1

ABBABBABBABB

範例輸出1

ABB

範例輸入1

ABCBABCBA

範例輸出1

ABCBABCBA

配分方法

0% 範例資料
30% $L\leq 10$
50% $L\leq 1000$
70% $L\leq 10^6$
100% $L\leq 5*10^7$

Judge Setting

run-time limit: 3000 ms
memory limit: 76972032 byte
測資數量: 0