Problem G
Gen

Fyrir illmenni sem ætla sér heimsyfirráð er algeng leið til að forðast handtöku að klóna sig. Þú hefur handsamað illmenni og $N-1$ klóna þess og ert nú að reyna finna hver er alvöru illmennið.

Þér til hjálpar hefurðu DNA röð hverrar persónu, hver þeirra samanstendur af $M$ táknum, hver stafur er A, C, G eða T. Þú veist einnig að klónarnir eru ekki skapaðir fullkomlega, heldur eru raðir þeirra frábrugðnar röð upprunalega illmennisins á nákvæmlega $K$ stöðum.

Getur þú auðkennt illmennið?

Inntak

Fyrsta línan inniheldur þrjár heiltölur $N$, $M$ og $K$ þar sem $1 \le K \le M$. Næstu $N$ línur tákna DNA raðirnar. Hver þessarra lína samanstendur af $M$ táknum, hvert þeirra er A, C, G eða T.

Í inntakinu er nákvæmlega ein röð sem er frábrugðin öllum hinum rununum á nákvæmlega $K$ stöðum.

Úttak

Skrifaðu út eina heiltölu – vísi DNA raðarinnar sem tilheyrir illmenninu. Fyrsta röðin er númer $1$.

Takmarkanir

Lausnin þín verður prófuð á einhvern fjölda prufuhópa, hver hópur gefur einhvern fjölda stiga. Hver hópur inniheldur einhvern fjölda prufutilvika. Til að fá stig fyrir hóp þarftu að leysa öll prufutilvik innan hópsins. Lokastigin eru fengin úr skilunum sem gáfu hæst stig.

4 3 1
ACC
CCA
ACA
AAA

3

4 4 3
CATT
CAAA
ATGA
TCTA

4