시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 1024 MB 20 8 7 77.778%

문제

For villains that intend to take over the world, a common way to avoid getting caught is to clone themselves. You have managed to catch an evil villain and her N−1 clones, and you are now trying to figure out which one of them is the real villain.

To your aid you have each person’s DNA sequence, consisting of M characters, each being either A, C, G or T. You also know that the clones are not perfectly made; rather, their sequences differ in exactly K places compared to the real villain’s.

Can you identify the real villain?

입력

The first line contains the three integers N, M, and K, where 1≤K≤M. The following N lines represent the DNA sequences. Each of these lines consists of M characters, each of which is either A, C, G or T.

In the input, there is exactly one sequence that differs from all the other sequences in exactly K places.

Warning: this problem has rather large amounts of input, and will require fast IO in Java.

출력

Output an integer – the index of the DNA sequence that belongs to the villain. The sequences are numbered starting from 1.

서브태스크 1 (27점)

  • 3 ≤ N, M ≤ 100

서브태스크 2 (19점)

  • 3 ≤ N, M ≤ 1800
  • All characters are either A or C.

서브태스크 3 (28점)

  • 3 ≤ N, M ≤ 4100
  • All characters are either A or C.

서브태스크 4 (26점)

  • 3 ≤ N, M ≤ 4100

예제 입력 1

4 3 1
ACC
CCA
ACA
AAA

예제 출력 1

3

예제 입력 2

4 4 3
CATT
CAAA
ATGA
TCTA

예제 출력 2

4