[BalticOI 2018] 基因工程
题目描述
**题目译自 [BalticOI 2018](https://boi2018.progolymp.se/tasks/) Day2「[Genetics](https://boi18-day2-open.kattis.com/problems/boi18.genetics)」**
给定 $N$ 个长度为 $M$ 的只由 ``A``、``T``、``G`` 和 ``C`` 组成的字符串,分别编号为 $1\ldots N$,其中一个是模式串,其它 $N-1$ 个字符串与模式串都恰好有 $K$ 个字符不同,找到这个模式串。
输入输出格式
输入格式
第一行包含三个整数 $N$, $M$ 和 $K$,满足 $1\leqslant K\leqslant M$。
接下来 $N$ 行,每行一个长度为 $M$ 的字符串。
数据保证模式串一定存在。
**警告:本题 IO 量较大,对于 Java 或 Python 语言,请使用较为快速的 IO 操作。**
输出格式
输出一个整数表示模式串的编号。
输入输出样例
输入样例 #1
4 3 1
ACC
CCA
ACA
AAA
输出样例 #1
3
输入样例 #2
4 4 3
CATT
CAAA
ATGA
TCTA
输出样例 #2
4
说明
## 限制与提示
|子任务|分值|数据范围|特殊约定|
|:----:|:--:|:------:|:------:|
|$1$ |$27$|$3\leqslant N,\,M\leqslant 100$|无|
|$2$ |$19$|$3\leqslant N,\,M\leqslant 1800$|所有字符串中只包含 ``A`` 和 ``C``|
|$3$ |$28$|$3\leqslant N,\,M\leqslant 4100$|所有字符串中只包含 ``A`` 和 ``C``|
|$4$ |$26$|$3\leqslant N,\,M\leqslant 4100$|无|
感谢 Hatsune_Miku 提供的翻译