You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

编辑距离（$\texttt{dis}$）

【题目描述】

定义两个长度为 $m$ 的字符串 $S,T$ 之间的编辑距离 $\mathrm{dis}(S,T)=\sum_{i=1}^m[S_i\ne T_i]$。

如果两个字符串之间的编辑距离恰好为 $k$，那么小 D 认为这两个字符串是“友好的”。

小 D 现在有 $n$ 个长度为 $m$ 的字符串 $S_1\sim S_n$，请你求出其中的一个字符串使得该字符串和其他 $n-1$ 个字符串都是“友好的”，保证答案存在且唯一。

由于小 D 很爱学生物，因此他保证这些字符串都只由字母 $\texttt{A},\texttt{C},\texttt{G},\texttt{T}$ 构成。

【输入格式】

从 $\texttt{dis.in}$ 中读入数据。

第一行三个整数 $n,m,k$。

接下来 $n$ 行，每行一个长度为 $m$ 的字符串表示 $S_1\sim S_n$。

【输出格式】

输出到 $\texttt{dis.out}$ 中。

输出一个整数表示所求的字符串的编号。

【样例 1 输入】

4 4 3
CATT
CAAA
ATGA
TCTA

【样例 1 输出】

4

【样例 2】

见下发文件中的 $\texttt{dis2.in}$ 与 $\texttt{dis2.ans}$。

该样例满足子任务 $2$ 的限制。

【样例 3】

见下发文件中的 $\texttt{dis3.in}$ 与 $\texttt{dis3.ans}$。

该样例满足子任务 $4$ 的限制。

【数据范围】

对于所有测试数据有：$3\le n,m\le 4100,1\le k\le m$，保证答案存在且唯一。

特殊性质 $\text A$：保证所有字符串仅由 $\texttt{A},\texttt{C}$ 构成。