#include <bits/stdc++.h> #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2") #define int long long #define pii pair<int,int> #define vi vector<int> #define ff first #define ss second #define sp << " " << #define all(x) x.begin(),x.end() #define big(x) ((int)(x.size())) using namespace std; const int MOD = 998244353, LIM = 1e6+1, inf = 2e18,N = 2e5+1; void solve() { int n,m,k; cin >> n >> m >> k; bitset<4000> bsts[n+1],bsts2[n+1]; vector<string> strs(n+1); stack<int> stk; for (int i=1;i<=n;i++) { cin >> strs[i]; for (int j = 0;j<m;j++) { bsts[i][j] = (strs[i][j] == 'A' || strs[i][j] == 'C'); bsts2[i][j] = (strs[i][j] == 'A' || strs[i][j] == 'G'); } } auto calcdiff =[&](int i,int j) -> int { return ((bsts[i]^bsts[j])|(bsts2[i]^bsts[j])).count(); }; vi ord(n+1); iota(all(ord),0ll); shuffle(1+all(ord),mt19937()); for (int i=1;i<=n;i++) { int fl = 1; while (!stk.empty() && calcdiff(stk.top(),ord[i]) != k) { stk.pop(); fl = 0; } if (fl) stk.push(ord[i]); } while (!stk.empty()) { int fl= 1; for (int j = 1;j<=n;j++) { if (j != stk.top() && calcdiff(stk.top(),j) != k) { fl = 0; break; } } if (fl) { cout << stk.top() << '\n'; return; } stk.pop(); } } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); int t = 1; //cin >> t; while (t --> 0) solve(); }