Zadanie

Detestujem radovky

Počet bodov: 25

Matúško je projektant. Ale malý, nepodstatný projektant v obrovskej podstatnej firme.

Čo však Matúškov podstatný šéf nevie, je to, že Matúško má narozdiel od zvyšku kúsok zmyslu pre estetiku. A tak, ako každý iný normálny človek, aj Matúško nenávidí pravidelné radovky.

Čo ale tiež Matúškov podstatný šéf nevie, je to, že po tom, čo v piatok odišiel skôr domov, sa Matúško vlámal do jeho kancelárie. A začal si prezerať dokumenty. A našiel plán výstavby na novej ulici, ktorý pre každý pozemok hovoril, či tam má byť postavený dom alebo nie, prípadne označenie, že to ešte nie je rozhodnuté.

A tak sa Matúško rozhodol, že tento plán musí zachrániť a prepísal všetky nerozhodnuté pozemky tak, aby sa celý plán neopakoval s periódou \(p\).

Plán sa opakuje s periódou \(p\), ak je každý znak v pláne rovnaký, ako ten o \(p\) pozícií vľavo.

Vstup a výstup

Na prvom riadku vstupu sa nachádzajú dve celé čísla oddelené medzerou – \(n\) a \(p\) (\(1 \leq p \leq n \leq 2 \cdot 10^5\)) – dĺžku reťazca a dĺžku periódy. Na druhom riadku sa nachádza reťazec \(s\) dĺžky \(n\) zložený zo znakov 0, 1 a ..

Ako výstup vypíšte reťazec \(s\), kde sú všetky znaky . nahradené znakom 0 alebo 1 tak, aby neobsahoval periódu dĺžky \(p\). Ak existuje viacero možných riešení, vypíšte ľubovoľné z nich. Naopak, ak neexistuje žiadne riešenie, vypíšte reťazec Nevydalo.

Obmedzenia

Približne v tretine vstupov platí \(n \leq 20\) a v ďalšej tretine \(n \leq 5000\).

Príklady

Input:

4 2
101.

Output:

1011

Toto je jediné možné riešenie, ak by sme tam dali nulu, 10 je periódou dĺžky 2.

Input:

5 5
.1...

Output:

Nevydalo

Keďže \(p = n\), určite bude celý reťazec periódou, takže neexistuje žiadne riešenie.

Input:

5 4
.1..1

Output:

01111

Keďže \(p[0] \neq p[4]\), reťazec nemá periódu 4.