#include <iostream>
#include <algorithm>
#include <cstdlib>
const int MAXN = 4100;
const int MAXT = 16400;
int dna[MAXN][MAXT];
int randomVector[MAXN];
int randDna[MAXT];
int randDiff[MAXN];
int search(int sequences, int size, int diff)
{
int sum = 0;
for (int iSeq = 0; iSeq < sequences; iSeq++)
{
randomVector[iSeq] = rand() * rand() * rand();
sum += (size - diff) * randomVector[iSeq];
}
for (int iChar = 0; iChar < size; iChar++)
{
randDna[iChar] = 0;
for (int iSeq = 0; iSeq < sequences; iSeq++)
randDna[iChar] += dna[iSeq][iChar] * randomVector[iSeq];
}
for (int iSeq = 0; iSeq < sequences; iSeq++)
{
randDiff[iSeq] = 0;
for (int iChar = 0; iChar < size; iChar++)
randDiff[iSeq] += dna[iSeq][iChar] * randDna[iChar];
}
int answer = -1;
for (int iSeq = 0; iSeq < sequences; iSeq++)
if (randDiff[iSeq] == sum + diff * randomVector[iSeq])
{
if (answer == -1)
answer = iSeq;
else
return -1;
}
return answer;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cout.tie(nullptr);
std::cin.tie(nullptr);
int sequences, size, differences;
std::cin >> sequences >> size >> differences;
for (int iSeq = 0; iSeq < sequences; iSeq++)
for (int iChar = 0; iChar < size; iChar++)
{
char elem; std::cin >> elem;
for (int iTrs = 0; iTrs < 4; iTrs++)
dna[iSeq][4 * iChar + iTrs] = -1;
switch (elem)
{
case 'A':
dna[iSeq][4 * iChar] = 1;
break;
case 'G':
dna[iSeq][4 * iChar + 1] = 1;
break;
case 'C':
dna[iSeq][4 * iChar + 2] = 1;
break;
case 'T':
dna[iSeq][4 * iChar + 3] = 1;
break;
}
}
srand(42);
int answer = search(sequences, 4 * size, 4 * differences);
while (answer == -1)
answer = search(sequences, 4 * size, 4 * differences);
std::cout << answer + 1 << '\n';
return 0;
}
