Baltic Olympiad in Informatics 2018 Open - day 2

Start

2018-04-29 07:30 UTC

Baltic Olympiad in Informatics 2018 Open - day 2

End

2018-04-29 12:30 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -300 days 1:53:05

Time elapsed

5:00:00

Time remaining

0:00:00

Problem B
Genetyka

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ę?

Input

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).

Output

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

Constraints

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group. Your final score will be the maximum score of a single submission.

Group

Points

Limits

Additional Constraints

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$

 
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