26191번 - Differences 다국어

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$