Problem G
Genetik

Schurken, die die Weltherrschaft übernehmen wollen, lassen sich gerne klonen, um der Gefangennahme zu entgehen. Du hast es geschafft, eine böse Schurkin zusammen mit ihren $N-1$ Klonen zu fassen, und möchtest nun herausfinden, welche von ihnen das Original ist.

Hilfreicherweise hast du die DNA-Sequenzen aller Personen, die jeweils aus $M$ Zeichen bestehen, jedes entweder A, C, G oder T. Außerdem weißt du, dass die Klone nicht perfekt sind; stattdessen unterscheiden sich die DNA-Sequenzen eines Klons an genau $K$ Stellen vom Original.

Kannst du das Original identifizieren?

Eingabe

Die erste Zeile enthält drei ganze Zahlen $N$, $M$, und $K$, wobei $1 \le K \le M$ gilt. Die folgenden $N$ Zeilen beschreiben die DNA-Sequenzen. Jede dieser Zeilen besteht aus $M$ Zeichen, von denen jede entweder A, C, G oder T ist.

In der Eingabe gibt es genau eine Sequenz, die sich von allen anderen in genau $K$ Stellen unterscheidet.

Warnung: Diese Aufgabe hat eine große Eingabe, und wird in Java schnelle Ein- und Ausgaberoutinen erfordern.

Ausgabe

Gib eine ganze Zahl aus: Den Index der DNA-Sequenz, die zu der Original-Schurkin gehört. Die Sequenzen sind von $1$ beginnend nummeriert.

Beschränkungen

Deine Lösung wird auf mehreren Testgruppen ausgeführt werden, von denen jede eine bestimmte Punktzahl wert ist. Jede Testgruppe enthält mehrere Testcases. Um Punkte für eine Testgruppe zu bekommen, müssen alle Testfälle in der entsprechenden Gruppe gelöst werden. Deine finale Punktzahl wird die maximal erreichte Punktzahl in einer einzelnen Einsendungen sein.

4 3 1
ACC
CCA
ACA
AAA

3

4 4 3
CATT
CAAA
ATGA
TCTA

4