#include <bits/stdc++.h>
using namespace std;
mt19937 rng(8962);
int n, m, k;
char a[4105][4105];
bitset<8205> bs[4105];
bitset<4105> f0[4105], f1[4105], f2[4105], f3[4105];
bool inbuf[4105];
bool mna(int x, int y)
{
int xx = (bs[x] ^ bs[y]).count() - (f0[x] & f1[y]).count() - (f1[x] & f0[y]).count() - (f2[x] & f3[y]).count() - (f3[x] & f2[y]).count();
if (xx == k)
return true;
return false;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m >> k;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> a[i][j];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
if (a[i][j] == 'A')
bs[i][2 * j - 1] = bs[i][2 * j] = 0;
else if (a[i][j] == 'C')
bs[i][2 * j] = 1;
else if (a[i][j] == 'G')
bs[i][2 * j - 1] = 1;
else
bs[i][2 * j - 1] = bs[i][2 * j] = 1;
if (a[i][j] == 'A')
f0[i][j] = 1;
if (a[i][j] == 'T')
f1[i][j] = 1;
if (a[i][j] == 'C')
f2[i][j] = 1;
if (a[i][j] == 'G')
f3[i][j] = 1;
}
set<int> buf;
for (int i = 1; i <= n; i++)
{
vector<int> alti;
for (int j = 1; j <= n; j++)
if (j != i and !inbuf[j])
alti.push_back(j);
shuffle(alti.begin(), alti.end(), default_random_engine(rng()));
bool ok = true;
for (auto it : buf)
{
if (it != i and !mna(i, it))
{
ok = false;
buf.insert(it);
break;
}
}
for (auto it : alti)
{
if (!mna(i, it))
{
ok = false;
buf.insert(it);
inbuf[it] = true;
break;
}
}
if (ok)
{
cout << i;
return 0;
}
}
return 0;
}
