Hide

Problem G
Genetikk

Languages de en et is ja lt lv no pl ru sv

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.

Group

Points

Limits

Yttligere begrensninger

1

27

$3 \le N, M \le 100$

 

2

19

$3 \le N, M \le 1800$

Hvert tegn er enten A eller C.

3

28

$3 \le N, M \le 4100$

Hvert tegn er enten A eller C.

4

26

$3 \le N, M \le 4100$

 
Sample Input 1 Sample Output 1
4 3 1
ACC
CCA
ACA
AAA
3
Sample Input 2 Sample Output 2
4 4 3
CATT
CAAA
ATGA
TCTA
4