#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

using ll = long long;
using ld = long double;
using pl = pair<ll, ll>;
using vl = vector<ll>;

#define f first
#define s second

ll n, m, k;

bool bad[100005];
using ul = unsigned long long;
vector<ul> bs[100005];
ll sz;
bool vis[5005][5005], rs[5005][5005];

mt19937 rng(53);

bool cmp(ll a, ll b) {
    if (a > b) swap(a, b);
    if (n <= 5000) {
        if (vis[a][b]) return rs[a][b];
        vis[a][b] = 1;
        ll ans = 0;
        for (ll i = 0; i < sz; i++) ans += __builtin_popcountll(bs[a][i] ^ bs[b][i]);
        // cout << a << " " << b << " " << ans << " " << k << endl;
        return rs[a][b] = (ans == k);
    } else {
        ll ans = 0;
        for (ll i = 0; i < sz; i++) ans += __builtin_popcountll(bs[a][i] ^ bs[b][i]);
        // cout << a << " " << b << " " << ans << " " << k << endl;
        return ans == k;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m >> k;
    k *= 2;

    sz = (m + 15) / 16;

    for (ll i = 0; i < n; i++) {
        string s; cin >> s;
        bs[i] = vector<ul>(sz);
        for (ll j = 0; j < m; j++) {
            ul v = 1 << (s[j] - 'A');
            bs[i][j / 16] += v << (4 * (j % 16));
        }
    }

    ll s = n;

    vl a(n);
    iota(a.begin(), a.end(), 0);

    vector<pl> lv;

    const ll K = 30;

    while (s > 1) {
        // cout << s << " " << a.size() << endl;
        ll x = -1, y = -1;
        if (!lv.size()) {
            x = rng() % a.size();
            while (bad[a[x]]) x = rng() % a.size();
            x = a[x];
            y = rng() % n;
            while (x == y) y = rng() % n;
        } else {
            y = lv.back().f;
            x = rng() % a.size();
            while (bad[a[x]] || a[x] == y) x = rng() % a.size();
            x = a[x];
        }

        if (!cmp(x, y)) {
            if (!bad[x]) {
                lv.push_back({x, K});
                --s;
            }
            if (!bad[y]) {
                --s;
                lv.push_back({y, K});
            }
            if (lv.size() && y == lv.back().f) lv.back().s = K;
            bad[x] = bad[y] = 1;
        } else {
            if (lv.size() && y == lv.back().f) {
                if (--lv.back().s == 0) lv.pop_back();
            }
        }

        if (s * 2 <= a.size()) {
            vl b;
            for (ll x: a) if (!bad[x]) b.push_back(x);
            a = b;
            s = a.size();
        }
    }

    cout << a[0] + 1 << '\n';
}