#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,popcnt")
#include "bits/extc++.h"
using namespace std;
template <typename T>
void dbgh(const T& t) {
cerr << t << endl;
}
template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
cerr << t << " | ";
dbgh(u...);
}
#ifdef DEBUG
#define dbg(...) \
cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
<< ": "; \
dbgh(__VA_ARGS__)
#else
#define cerr \
if (false) \
cerr
#define dbg(...)
#endif
#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())
const int maxn = 4105;
int n, m, k;
char arr[maxn][maxn];
namespace s1 {
const string chars = "ACGT";
const long mod = 1e9 + 7;
bitset<maxn> arrb[maxn][4];
long hsh(int ind) {
long h1 = 0, h2 = 0;
for (int i = 0; i < m; i++) {
h1 = (h1 * 7 + int(chars.find(arr[ind][i])) + 1) % mod;
h2 = (h2 * 11 + int(chars.find(arr[ind][i])) + 1) % mod;
}
return h1 * mod + h2;
}
void solve() {
mt19937 cowng(chrono::steady_clock::now().time_since_epoch().count());
int ord[n], conv[n];
bool bad[n] {}, checked[n][n] {};
iota(ord, ord + n, 0);
shuffle(ord, ord + n, cowng);
int cind = 0;
map<long, int> vis;
for (auto& a : ord) {
auto [it, inserted] = vis.emplace(hsh(a), cind);
if (!inserted) {
bad[it->second] = true;
continue;
}
for (int c = 0; c < 4; c++) {
for (int j = 0; j < m; j++) {
if (arr[a][j] == chars[c]) {
arrb[cind][c].set(j);
}
}
}
conv[cind] = a;
cind++;
}
dbg(cind);
k *= 2;
for (int i = 0; i < cind; i++) {
if (bad[i]) {
continue;
}
for (int j = 0; j < cind; j++) {
if (i == j || checked[i][j]) {
continue;
}
int cnt = 0;
for (int a = 0; a < 4; a++) {
cnt += int((arrb[i][a] ^ arrb[j][a]).count());
if (cnt > k) {
break;
}
}
checked[i][j] = checked[j][i] = true;
if (cnt != k) {
bad[j] = true;
goto loop;
}
}
cout << conv[i] + 1 << endl;
return;
loop:;
}
}
} // namespace s1
namespace s2 {
const int maxb = maxn;
bitset<maxb> arrb[maxb];
void solve() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (arr[i][j] == 'A') {
arrb[i].set(j);
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i != j) {
int cnt = int((arrb[i] ^ arrb[j]).count());
if (cnt != k) {
goto loop;
}
}
}
cout << i + 1 << endl;
return;
loop:;
}
}
} // namespace s2
void solve() {
cin >> n >> m >> k;
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
bool b = true;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
b &= arr[i][j] == 'A' || arr[i][j] == 'C';
}
}
if (b) {
s2::solve();
} else {
s1::solve();
}
}
int main() {
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
cin.exceptions(ios::failbit);
solve();
}
