Problem F
Genetikk

En vanlig teknikk som superskurker bruker for å unngå å bli fanget er å klone seg selv. Du har klart å fange en ond superskurk og hennes $N-1$ kloner, men du ønsker å finne ut hvem av de som er den ekte superskurken.

Til hjelp har du hver persons DNA-sekvens, som hver består av $M$ tegn, hvor hvert tegn er enten A, C, G eller T. Du vet også at klonene aldri er helt perfekte kopier, men at de har DNA-sekvenser som skiller seg fra den ekte superskurken på nøyaktig $K$ posisjoner.

Kan du identifisere den ekte superskurken?

Input

Første linje inneholder tre heltall $N$, $M$, og $K$, hvor $1 \le K \le M$. De neste $N$ linjene representerer DNA sekvenser. Hver av disse linjene inneholder $M$ tegn, hvor hvert tegn er enten A, C, G eller T.

I input vil det være nøyaktig én sekvens som skiller seg fra alle de andre sekvensene i nøyaktig $K$ posisjoner.

Advarsel: dette problemet har ganske mye input og vil kreve at du bruker raske IO-rutiner om du bruker Java.

Output

Skriv ut et heltall – indeksen av DNA-sekvensen som tilhører superskurken. Sekvensene er numerert begynnende med $1$.

Begrensninger

Løsningen din vil bli testet på et sett av testgrupper, hver verdt et visst antall poeng. Hver testgruppe inneholder et sett av tester. For å få poeng for en testgruppe må du løse alle testene i den gruppen. Din endelige poengsum vil være den høyeste poengsummen du har fått på en enkelt innlevering.

4 3 1
ACC
CCA
ACA
AAA

3

4 4 3
CATT
CAAA
ATGA
TCTA

4