P4795 [BalticOI 2018] Genetic Engineering

**This problem is translated from [BalticOI 2018](https://boi2018.progolymp.se/tasks/) Day 2 “[Genetics](https://boi18-day2-open.kattis.com/problems/boi18.genetics)”.** You are given $N$ strings of length $M$, consisting only of `A`, `T`, `G`, and `C`, numbered $1 \ldots N$. One of them is the pattern string. Each of the other $N - 1$ strings differs from the pattern string in exactly $K$ characters. Find this pattern string.

The first line contains three integers $N$, $M$, and $K$, satisfying $1\leqslant K\leqslant M$. The next $N$ lines each contain a string of length $M$. It is guaranteed that the pattern string exists. **Warning: The I/O size of this problem is large. For Java or Python, please use faster I/O methods.**

Output one integer, the index of the pattern string.

Translated by ChatGPT 5