Problem Description

This problem is translated from BalticOI 2018 Day 2 “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.

Input Format

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 Format

Output one integer, the index of the pattern string.

4 3 1
ACC
CCA
ACA
AAA

3

4 4 3
CATT
CAAA
ATGA
TCTA

4

Hint

Translated by ChatGPT 5