유전학

면접 대비

시간 제한2초메모리 제한1024 MB

요약

길이 M인 DNA 문자열 N개가 주어질 때, 다른 모든 문자열과 정확히 K개 위치에서 다른 문자열 하나를 찾는다.

문제

세계를 정복하려는 악당들이 발각을 피하는 흔한 방법은 자신을 복제하는 것이다. 당신은 사악한 악당 한 명과 그 악당의 클론 $N-1$ 명을 붙잡았고, 그 중에서 진짜 악당이 누구인지 가려내야 한다.

단서는 각자의 DNA 서열이다. 각 서열은 길이가 $M$ 이며, 각 문자는 A, C, G, T 중 하나이다. 또한 클론은 완벽한 복제가 아니어서, 진짜 악당의 서열과 정확히 $K$ 곳이 다르다는 사실도 알고 있다.

진짜 악당을 찾아낼 수 있는가?

첫째 줄에 세 정수 $N$ , $M$ , $K$ 가 주어진다. 단, $1 \le K \le M$ 이다. 다음 $N$ 줄에는 DNA 서열이 한 줄에 하나씩 주어진다. 각 서열은 길이가 $M$ 이며 A, C, G, T로만 이루어져 있다.

입력에는 나머지 모든 서열과 정확히 $K$ 곳이 다른 서열이 정확히 하나 존재함이 보장된다.

주의: 이 문제의 입력은 다소 크므로, 빠른 입력 방식을 사용해야 한다.

진짜 악당의 DNA 서열 번호를 나타내는 정수를 출력한다. 서열 번호는 $1$ 부터 시작한다.