Differences
Description
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.
Input limits
- $2 \leq N, M \leq 10^5$
- $1 \leq K \leq M$
- $NM \leq 2 \cdot 10^7$
Output the index $i$ of the special string. Strings are numbered from $1$ to $N$ as given in the input.
Input
The first line contains space-separated integers $N$, $M$ and $K$. Strings $S_i$ are given in the following $N$ lines.
Input limits
- $2 \leq N, M \leq 10^5$
- $1 \leq K \leq M$
- $NM \leq 2 \cdot 10^7$
Output
Output the index $i$ of the special string. Strings are numbered from $1$ to $N$ as given in the input.
5 10 2
DCDDDCCADA
ACADDCCADA
DBADDCCBDC
DBADDCCADA
ABADDCCADC
4 6 5
AABAAA
BAABBB
ABAAAA
ABBAAB
4
2