题目描述

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.

5 10 2
DCDDDCCADA
ACADDCCADA
DBADDCCBDC
DBADDCCADA
ABADDCCADC

4

4 6 5
AABAAA
BAABBB
ABAAAA
ABBAAB

2

提示

Input limits

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