P13810 [CERC 2022] 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.

### Input limits * $2 \leq N, M \leq 10^5$ * $1 \leq K \leq M$ * $NM \leq 2 \cdot 10^7$