Hide

Problem G
Genetyka

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

Złoczyńcy, którzy dążą do podboju świata, oczywiście nie chcą być złapani. Znaną i powszechnie stosowaną metodą, aby tego dokonać, jest klonowanie samego siebie. Udało Ci się złapać złoczyńcę oraz jego $N-1$ klonów i teraz próbujesz wydedukować, który z nich jest prawdziwym złoczyńcą.

Łańcuch DNA każdej złapanej osoby składa się z $M$ znaków, każdy z nich to A, C, G lub T. Wiesz także, że klony nie są perfekcyjne; w szczególności ich sekwencje DNA różnią się od DNA prawdziwego złoczyńcy na dokładnie $K$ pozycjach.

Czy potrafisz zidentyfikować prawdziwego złoczyńcę?

Wejście

W pierwszym wierszu dane są trzy liczby całkowite $N$, $M$ oraz $K$, gdzie $1 \le K \le M$. W następnych $N$ wierszach znajdują się sekwencje DNA. Każdy z tych wierszy składa się z $M$ znaków A, C, G lub T.

Wśród sekwencji z wejścia jest dokładnie jedna sekwencja, która różni się od pozostałych na dokładnie $K$ pozycjach.

Uwaga: ponieważ limity wejściowe są całkiem duże, Java może wymagać szybkiego wczytywania wejścia (fast IO).

Wyjście

Wypisz jedną liczbę całkowitą – indeks sekwencji DNA, który należy do prawdziwego złoczyńcy. Sekwencje są ponumerowane, poczynając od $1$.

Ograniczenia

Zestaw testów dzieli się na kilka grup, każda jest warta pewną liczbę punktów. Każda grupa składa się z jednego bądź większej liczby testów. Aby otrzymać punkty za daną grupę, Twoje rozwiązanie musi przejść wszystkie testy z tej grupy. Ostateczny wynik za zadanie jest liczony jako maksymalny wynik z pojedynczych zgłoszeń.

Grupa

Punkty

Limity

Dodatkowe ograniczenia

1

27

$3 \le N, M \le 100$

 

2

19

$3 \le N, M \le 1800$

Wszystkie znaki to A lub C.

3

28

$3 \le N, M \le 4100$

Wszystkie znaki to A lub C.

4

26

$3 \le N, M \le 4100$

 
Przykładowe wejście 1 Przykładowe wyjście 1
4 3 1
ACC
CCA
ACA
AAA
3
Przykładowe wejście 2 Przykładowe wyjście 2
4 4 3
CATT
CAAA
ATGA
TCTA
4