Problem G
Guessing Passwords

Mynd tekin frá commons.wikimedia.org.

Ingfríður er að prófa nýju heimasíðu sína, Passwordle. Reglurnar gætu hljómað kunnulega fyrir þá sem eru vanir orðlu, en skulum fara yfir þær hér. Síðan velur leynilegt lykilorð sem notandinn þarf að giska. Lykilorðið er $N$ stafir að lengd og notandinn giskar aftur og aftur þar til þeir giska rétt, og því færri gisk því betra. Sérhvert gisk þarf að vera strengur $N$ stafa. Sérhver stafur í giskinu fær einn af þremur litum. Ef stafurinn passar við samsvarandi staf í lykilorðinu er stafurinn litaður grænn. Ef stafurinn er í lykilorðinu, en stafurinn er ekki á réttum staf er stafurinn litaður gulur. Ef stafurinn kemur ekki fyrir í lykilorðinu er hann litaður grár.

Ingfríður er auðvitað mjög góð í Passwordle, svo hún mun ávallt giska á lykilorð sem gæti verið rétta lykilorðið. Því samsvarast gisk hennar ávallt öllum fyrri upplýsingum sem fást útfrá litum. Ennfremur veit hún að forritið velur aldrei lykilorð með sama staf á fleir en einum stað, þar sem það er óörrugt, og hún beitir þeirri þekkingu í giskum sínum.

Hún sendi þér nýlega skjáskot af prófunarferli sínu, en myndirnar þjöppuðust svo hryllilega að þú getur bara séð litina en ekki stafina sjálfa. Enn fremur virðist hún ekki hafa náð neinum árangri. Hún náði ekki einum einasta grænum staf og fann ekki fleri rétta stafi en hún var þegar með í fyrsta giski. Hún hætti í pirringskasti greinilega, svo fjöldi gulra reita í hverri röð er sú sama. Að þessum upplýsingum gefnum getur þú fundið út úr því hvað giskin hefðu getað verið? Eða eru engin gild gisk sem myndu gefa þessa liti og það er villa í forritinu? Þú mátt gera ráð fyrir að Ingfríður geri aldrei mistök þegar hún spilar Passwordle, bara þegar hún forritar.

Inntak

Fyrsta lína inntaksins inniheldur tvær jákvæðar heiltölur $N$ og $M$ ($1 \leq N, M \leq 100$). $N$ er fjöldi stafa í lykilorðinu og $M$ er fjöldi giska í skjáskotinu. Næst koma $N$ línur, hver með $M$ stöfum, þar sem $i$-ta línan gefur liti $i$-ta gisksins. G táknar gráan og Y táknar gulan. Fjöldi Y-a er eins í öllum línum. Stafirnir eru gefnir án bila milli þeirra. Loks er ein lína með einni jákvæðri heiltölu $\Sigma $ ($1 \leq \Sigma \leq 10^6$) sem gefur fjölda gildra stafa sem má nota í lykilorðunum.

Úttak

Ef ekki er til nein leið til að mynda gefnu litina, prentið Bugged!. Annars prentið $N + 1$ línur með $M$ tölum hver, aðskilin með bilum. Fyrstu $N$ línurnar ættu að mynda litunina í inntakinu þar sem talan $i$ táknar $i$-ta gilda stafinn sem má nota. Síðasta og $(N+1)$-ta línan ætti að gefa lykilorð sem hefði getað verið rétta leynilega lykilorðið. Ef það eru mörg rétt svör má skila hverju sem er þeirra.

Útskýring á sýnidæmi

Í fyrsta sýnidæminu er til gild runa giska. Í fyrsta giski giskar Ingfríður á 3 4 2 1, sem gefur okkur að $1$ og $2$ eru í lykilorðinu en ekki á þessum stöðum. Næsta gisk er 1 5 6 2 sem er gilt gisk því það hefði getað verið leynilega lykilorðið að svo stöddu. Dæmi um ógilt annað gisk væri 1 3 2 5 þar sem Ingfríður veit þegar að tvisturinn er ekki í þriðja sæti lykilorðsins og að það er enginn þristur í lykilorðinu.

3 4
GGYY
YGGY
GYYG
26

3 4 2 1 
1 5 6 2 
7 2 1 8 
2 1 9 10 

4 5
GYGGY
YGYGG
GGYYG
GYGGY
16

Bugged!