题目描述
Problem Description
This problem is a translation from BalticOI 2018 Day2 "Genetics"
Given \( N \) strings of length \( M \) consisting only of the characters A, T, G, and C, numbered from \( 1 \) to \( N \), one of which is the pattern string. The other \( N-1 \) strings differ from the pattern string by exactly \( K \) characters. Find this pattern string.
Input Format
The first line contains three integers \( N \), \( M \), and \( K \), where \( 1 \leqslant K \leqslant M \).
The next \( N \) lines each contain a string of length \( M \).
It is guaranteed that a pattern string always exists.
Warning: This problem has a large IO volume. For Java or Python, please use fast IO operations.
Output Format
Output a single integer representing the number of the pattern string.
Sample Input and Output
Sample Input #1
4 3 1
ACC
CCA
ACA
AAA
Sample Output #1
3
Sample Input #2
4 4 3
CATT
CAAA
ATGA
TCTA
Sample Output #2
4
Notes/Hints
| Subtask | Score | Data Range | Special Constraints |
|---|---|---|---|
| 1 | 27 | \( 3 \leqslant N, M \leqslant 100 \) | None |
| 2 | 19 | \( 3 \leqslant N, M \leqslant 1800 \) | All strings contain only A and C |
| 3 | 28 | \( 3 \leqslant N, M \leqslant 4100 \) | All strings contain only A and C |
| 4 | 26 | \( 3 \leqslant N, M \leqslant 4100 \) | None |
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分