Hide

Problem G
Генетика

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

Клонирование себя – способ маскировки, которым часто пользуются ужасные злодеи, собирающиеся захватить вселенную. Вы недавно захватили ужасного злодея вместе с его $N-1$ клонами, и пытаетесь узнать, кто же из них всех является оригинальным злодеем, а кто – клоны.

К счастью, у вас есть доступ к последовательностям ДНК всех подозреваемых. Каждая последовательность состоит из $M$ символов A, C, G или T. Известно, что клоны сделаны неидеально – их ДНК отличается от оригинала ровно в $K$ позициях.

Можете ли вы распознать настоящего злодея?

Ввод

На первой строке даны три целых числа $N$, $M$, и $K$, где $1 \le K \le M$. На следующих $N$ строках даны последовательности ДНК. Каждая из них состоит из $M$ символов A, C, G или T.

Только одна из данных в файле последовательностей отличается от каждой из остальных ровно в $K$ позициях.

Внимание: объем входных данных в этой задаче довольно большой и требует использования быстрых библиотек ввода-вывода в Java.

Вывод

Выведите целое число – номер ДНК последовательности настоящего злодея. Последовательности нумеруются с $1$.

Ограничения

Тесты разделены на группы. Очки за группу даются только если корректно решены все тесты в группе.

Группа

Очки

Ограничения

Дополнительные ограничения

1

27

$3 \le N, M \le 100$

 

2

19

$3 \le N, M \le 1800$

Только символы A и C.

3

28

$3 \le N, M \le 4100$

Только символы A и C.

4

26

$3 \le N, M \le 4100$

 
Пример ввода 1 Пример вывода 1
4 3 1
ACC
CCA
ACA
AAA
3
Пример ввода 2 Пример вывода 2
4 4 3
CATT
CAAA
ATGA
TCTA
4