#include <bits/stdc++.h>
using namespace std;
/*
trying the bitset idea with the subtasks "dna has only A or C" worked for the smaller one, but failed
for the larger one until i cut the constant in half by only checking i+1..n, and precomputing counts for
those smaller than me. so now that its 4 bitsets not 1, maybe i can eliminate a bitset or 2 and also shuffling the order
means we expect to find the correct one within the first half of the array, halving the expected time
*/
using ull = unsigned long long;
struct b {
static const int MAXM = 4100;
static const int W = (MAXM + 63) / 64;
ull x[W];
b() {
memset(x, 0, sizeof(x));
}
struct Ref {
ull &word;
int bit;
Ref(ull &word, int bit) : word(word), bit(bit) {}
Ref& operator=(bool v) {
if (v) word |= 1ULL << bit;
else word &= ~(1ULL << bit);
return *this;
}
operator bool() const {
return (word >> bit) & 1ULL;
}
};
Ref operator[](int pos) {
return Ref(x[pos >> 6], pos & 63);
}
bool operator[](int pos) const {
return (x[pos >> 6] >> (pos & 63)) & 1ULL;
}
};
inline int dist(const b &a1, const b &b1, const b &a2, const b &b2, int k) {
int res = 0;
for (int i = 0; i < b::W; i++) {
ull cur = (a1.x[i] ^ b1.x[i]) | (a2.x[i] ^ b2.x[i]);
res += __builtin_popcountll(cur);
if (res > k) return res;
}
return res;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int n, m, k; cin >> n >> m >> k;
vector<string> seq(n); for (int i = 0; i < n; i++) cin >> seq[i];
// using b = bitset<4100>;
vector<int> idx(n); iota(idx.begin(), idx.end(), 0);
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
shuffle(idx.begin(), idx.end(), rng);
vector<b> s1(n), s2(n);
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
auto c = seq[idx[i]][j];
if (c == 'C' || c == 'T') s1[i][j] = 1;
if (c == 'G' || c == 'T') s2[i][j] = 1;
}
vector<int> cnt(n);
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n; j++) {
int t = 0;
t += dist(s1[i], s1[j], s2[i], s2[j], k);
if (t == k) cnt[i]++, cnt[j]++;
}
if (cnt[i] == n-1) {
cout << idx[i]+1 << "\n";
break;
}
}
return 0;
}
