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$

힌트