6. Centrifúgy sa dotočia

V útrobách švajčiarskych hôr, na nevypátrateľnom mieste, prebieha každoročné zasadnutie Konzorcia Svetového Poriadku. Postavy zahalené v tme sedia po obvode kruhového stola a v miestnosti sa ozýva iba kovové chrapčanie modifikátorov hlasu. Svet čelí veľkým výzvam, imigrácii či globálnemu otepľovaniu, oni sú tu však na to, aby zabraňovali oveľa vážnejším, skrytým hrozbám.

Najnovšie správy od agentov v utajení uvádzajú rozmah nelegálnych centier spracovávajúcich rádioaktívny materiál. A je jasné, že takto získaný obohatený urán má len jediný cieľ. Je na čase, aby KSP zakročilo. Ich zásah musí však byť nenápadný. Nemôžu si predsa dovoliť, aby sa krajiny začali navzájom obviňovať a spôsobili ešte väčší chaos.

Ich riešenie je jednoduché. Vytvoria počítačový vírus, ktorý sa bude šíriť po sieti, či pomocou infikovaných USB kľúčov. Jeho úlohou bude vyhľadávať počítače, na ktoré sú napojený centrifúgy používané na oddeľovanie rádioaktívneho materiálu a tieto centrifúgy zneškodňovať.

Centrifúga je pomerne jednoduché zariadenie. Po zapnutí začne postupne zvyšovať otáčky rotácie, až kým od kontrolného zariadenia nedostane signál na zastavenie. Aby sa zaručilo, že centrifúga bude spomaľovať plynule, signál na zastavenie pozostáva z viacerých znakov. Presnejšie, každá centrifúga má určené slovo \(S\), ktoré sa používa na jej zastavanie. Kontrolný počítač vysiela centrifúge každú sekundu jedno písmeno a v prípade, že tieto písmená vytvoria slovo \(S\), centrifúga zastane.

Cieľom navrhovaného vírusu by bolo zmeniť postupnosť písmen vyslaných kontrolným počítačom tak, aby centrifúga nezastavila, ale zrýchľovala tak dlho, až kým nedôjde k jej poškodeniu. Všetky vyslané signály sa však zaznamenávajú do logov, v záujme utajenia by preto bolo dobré, aby zmenené signály predsa len obsahovali slovo \(S\). To však znie ako nemožná úloha – ako navrhnúť signál tak, aby obsahoval a zároveň neobsahoval slovo \(S\)? Našťastie, agentom KSP sa podarilo získať zdrojové kódy centrifúg a nazdávajú sa, že časť overujúca signály je implementovaná zle.

Úloha

Na vstupe dostanete slovo \(S\) skladajúce sa z veľkých písmen anglickej abecedy. Vašou úlohou je vytvoriť najkratší možný (lebo nenápadnosť) reťazec \(X\), ktorý obsahuje slovo \(S\) ako súvislý podúsek, ale nižšie uvedený program o ňom prehlási, že reťazec \(S\) neobsahuje.

K dispozícii máte ekvivalentné programy v jazykoch C++ aj Python. V oboch prípadoch je implementovaná funkcia obsahuje(S, X), ktorá vracia True ak si myslí, že \(X\) obsahuje \(S\) a False, keď si myslí, že ho neobsahuje.

def obsahuje(S, X):
    ps, px = 0, 0
    while True:
        if ps == len(S):
            return True
        if px == len(X):
            return False
        if S[ps] == X[px]:
            ps += 1
            px += 1
        elif ps == 0:
            px += 1
        else:
            ps = 0

bool obsahuje(string S, string X) {
    int ps = 0, px = 0;
    while (true) {
        if (ps == S.length())
            return true;
        if (px == X.length())
            return false;
        if (S[ps] == X[px]) {
            ps += 1;
            px += 1;
        }
        else if (ps == 0) {
            px += 1;
        }
        else {
            ps = 0;
        }
    }
}

Formát vstupu

Na jedinom riadku vstupu sa nachádza slovo \(S\) tvorené \(n\) (\(1 \leq n \leq 500\,000\)) veľkými písmenami anglickej abecedy.

V polovici testovacích vstupov platí, že \(n\) je nanajvýš \(2\,000\).

Formát výstupu

Na výstup vypíšte do jedného riadku najkratšie možné slovo \(X\), ktoré spĺňa požadované podmienky. V prípade, že takéto slovo neexistuje, na výstup vypíšte hlášku Centrifuga sa nepokazi!.

Príklady

Input:

AAB

Output:

AAAB

Input:

CENTRIFUGA

Output:

Centrifuga sa nepokazi!