Problem G
Genetik

Vissa förbrytare vill ta över världen. Ett vanligt sätt för förbrytare att undvika att bli straffade är att klona sig själva. Du har nu fångat en förbrytare och hennes $N-1$ kloner. Du ska ta reda på vem av dem som är den riktiga förbrytaren.

Du har tillgång till varje infångad persons DNA, som består av $M$ bokstäver där varje bokstav är antingen A, C, G eller T. Du vet också att klonerna inte är perfekta kopior, utan DNA-sekvensen för varje klon skiljer sig på exakt $K$ ställen jämfört med den riktiga förbrytaren.

Kan du identifiera den riktiga förbrytaren?

Indata

Den första raden innehåller tre heltal $N$, $M$ och $K$, där $1 \le K \le M$. Följande $N$ rader innehåller DNA-sekvenser. Varje av dessa innehåller $M$ bokstäver, där varje bokstav är någon av A, C, G or T.

Det finns, i inputen, exakt en sekvens som skiljer sig från alla andra på exakt $K$ ställen.

Varning: Det här problemet har stora mängder indata, och kräver snabb IO om man använder Java.

Utdata

Skriv ut ett heltal – indexet av DNA-sekvensen som tillhör förbrytaren. Sekvensernas index börjar med $1$.

Begränsningar

Din lösning kommer att testas på en uppsättning testgrupper, var och en värd en viss poäng. Varje testgrupp innehåller flera testfall. För att få poäng för en testgrupp måste du klara alla testfallen i gruppen. Din slutgiltiga poäng på problemet kommer att vara den maximala poängen av en enda submission.

4 3 1
ACC
CCA
ACA
AAA

3

4 4 3
CATT
CAAA
ATGA
TCTA

4