Differences

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

요약

길이가 같은 A~D 문자열 N개가 주어질 때, 다른 모든 문자열과의 거리가 정확히 K인 특별한 문자열의 번호를 찾는다(없으면 -1).

난이도: 보통10점 중 6점
유형: 구현, 수학
정답자: 아직 제출이 없습니다

문제

We have a list of $N$ strings $S\_i$ . All strings have length $M$ and consist only of characters A, B, C and D. Let us define the distance between two strings $X$ and $Y$ as the number of indices $j$ , where the strings have different characters ( $X\_j \neq Y\_j$ ). We know that the list of strings $S\_i$ contains precisely one special string that has distance $K$ to all other strings. Note that there might be other pairs of strings with a distance of $K$ . We are experiencing problems finding this special string, so please write a program to help us out.

입력

The first line contains space-separated integers $N$ , $M$ and $K$ . Strings $S\_i$ are given in the following $N$ lines.

출력

Output the index $i$ of the special string. Strings are numbered from $1$ to $N$ as given in the input.

제한

$2 \leq N, M \leq 10^5$
$1 \leq K \leq M$
$N M \leq 2 \cdot 10^7$

예제2

예제 1

입력

5 10 2
DCDDDCCADA
ACADDCCADA
DBADDCCBDC
DBADDCCADA
ABADDCCADC

예상 출력

예제 2
입력
```
4 6 5
AABAAA
BAABBB
ABAAAA
ABBAAB
```
예상 출력
```
2
```