#include <bits/stdc++.h>
using namespace std;
#define int int64_t //be careful about this
#define endl "\n"
#define f(i,a,b) for(int i=int(a);i<int(b);++i)
#define pr pair
#define ar array
#define fr first
#define sc second
#define vt vector
#define pb push_back
#define eb emplace_back
#define LB lower_bound
#define UB upper_bound
#define PQ priority_queue
#define SZ(x) ((int)(x).size())
#define all(a) (a).begin(),(a).end()
#define allr(a) (a).rbegin(),(a).rend()
#define mem(a,b) memset(a, b, sizeof(a))
template<class A> void rd(vt<A>& v);
template<class T> void rd(T& x){ cin >> x; }
template<class H, class... T> void rd(H& h, T&... t) { rd(h) ; rd(t...) ;}
template<class A> void rd(vt<A>& x) { for(auto& a : x) rd(a) ;}
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
template<typename T>
void __p(T a) {
cout<<a;
}
template<typename T, typename F>
void __p(pair<T, F> a) {
cout<<"{";
__p(a.first);
cout<<",";
__p(a.second);
cout<<"}\n";
}
template<typename T>
void __p(std::vector<T> a) {
cout<<"{";
for(auto it=a.begin(); it<a.end(); it++)
__p(*it),cout<<",}\n"[it+1==a.end()];
}
template<typename T, typename ...Arg>
void __p(T a1, Arg ...a) {
__p(a1);
__p(a...);
}
template<typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
cout<<name<<" : ";
__p(arg1);
cout<<endl;
}
template<typename Arg1, typename ... Args>
void __f(const char *names, Arg1 &&arg1, Args &&... args) {
int bracket=0,i=0;
for(;; i++)
if(names[i]==','&&bracket==0)
break;
else if(names[i]=='(')
bracket++;
else if(names[i]==')')
bracket--;
const char *comma=names+i;
cout.write(names,comma-names)<<" : ";
__p(arg1);
cout<<" | ";
__f(comma+1,args...);
}
void setIO(string s = "") {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin.exceptions(cin.failbit);
cout.precision(15); cout << fixed;
if(SZ(s)){
freopen((s+".in").c_str(),"r",stdin);
freopen((s+".out").c_str(),"w",stdout);
}
}
/**
* Description :- modular arithmetic operations
* Source :- https://codeforces.com/contest/1342/submission/78409946
* Verification:- https://open.kattis.com/problems/modulararithmetic
*/
template<const int &MOD>
struct _m_int {
int val;
_m_int(int64_t v = 0) {
if(v < 0) v = v % MOD + MOD;
if(v >= MOD) v %= MOD;
val = v;
}
static int inv_mod(int a, int m = MOD) {
// https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Example
int g = m, r = a, x = 0, y = 1;
while(r != 0) {
int q = g / r;
g %= r; swap(g, r);
x -= q * y; swap(x, y);
}
return x < 0 ? x + m : x;
}
// wont work if we use #define int int64_t
// explicit operator int() const { return val; }
explicit operator int64_t() const { return val; }
_m_int& operator+=(const _m_int &other) {
val -= MOD - other.val;
if(val < 0) val += MOD;
return *this;
}
_m_int& operator-=(const _m_int &other) {
val -= other.val;
if(val < 0) val += MOD;
return *this;
}
static unsigned fast_mod(uint64_t x, unsigned m = MOD) {
#if !defined(_WIN32) || defined(_WIN64)
return x % m;
#endif
// Optimized mod for Codeforces 32-bit machines.
// x must be less than 2^32 * m for this to work, so that x / m fits in a 32-bit unsigned int.
unsigned x_high = x >> 32, x_low = (unsigned) x;
unsigned quot, rem;
asm("divl %4\n"
: "=a" (quot), "=d" (rem)
: "d" (x_high), "a" (x_low), "r" (m));
return rem;
}
_m_int& operator*=(const _m_int &other) {
val = fast_mod((uint64_t) val * other.val);
return *this;
}
_m_int& operator/=(const _m_int &other) {
return *this *= other.inv();
}
friend _m_int operator+(const _m_int &a, const _m_int &b) { return _m_int(a) += b; }
friend _m_int operator-(const _m_int &a, const _m_int &b) { return _m_int(a) -= b; }
friend _m_int operator*(const _m_int &a, const _m_int &b) { return _m_int(a) *= b; }
friend _m_int operator/(const _m_int &a, const _m_int &b) { return _m_int(a) /= b; }
_m_int& operator++() {
val = val == MOD - 1 ? 0 : val + 1;
return *this;
}
_m_int& operator--() {
val = val == 0 ? MOD - 1 : val - 1;
return *this;
}
// wont work if we use #define int int64_t
// _m_int operator++(int) { _m_int before = *this; ++*this; return before; }
// _m_int operator--(int) { _m_int before = *this; --*this; return before; }
_m_int operator-() const {
return val == 0 ? 0 : MOD - val;
}
bool operator==(const _m_int &other) const { return val == other.val; }
bool operator!=(const _m_int &other) const { return val != other.val; }
_m_int inv() const {
return inv_mod(val);
}
_m_int pow(int64_t p) const {
if(p < 0) return inv().pow(-p);
_m_int a = *this, result = 1;
while(p > 0) {
if(p & 1) result *= a;
a *= a;
p >>= 1;
}
return result;
}
friend ostream& operator<<(ostream &os, const _m_int &m) {
return os << m.val;
}
};
extern const int MOD = int(1e9) + 7;
using mint = _m_int<MOD>;
#define rand __rand
auto random_address = [] { char *p = new char; delete p; return uint64_t(p); };
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count() * (random_address() | 1));
int rand(int L = 0,int R = int(1e9)){
return uniform_int_distribution<int>(L,R)(rng) ;
}
const int HASH_COUNT = 2;
const int BASE[] = {rand(0.1 * MOD, 0.9 * MOD), rand(0.1 * MOD, 0.9 * MOD)};
const string LETTERS = "ATGC";
signed main(){
setIO();
int N,M,K;
rd(N,M,K);
K = M-K; // number of same chars.
vt<mint> pow[2];
for(int i = 0; i < HASH_COUNT; ++i){
for(int j = 0; j < N; ++j){
pow[i].pb(mint(BASE[i]).pow(j));
}
}
vt<string> s(N);
rd(s);
vt<vt<mint>> a[HASH_COUNT];
for(int i = 0; i < HASH_COUNT; ++i){
a[i] = vt<vt<mint>>(M,vt<mint>(N));
}
vt<mint> total[HASH_COUNT][SZ(LETTERS)];
for(int j = 0; j < HASH_COUNT; ++j){
for(int i = 0; i < SZ(LETTERS); ++i){
total[j][i] = vt<mint> (M);
}
}
// value if a[i][j] is activated.
for(int i = 0; i < M; ++i){
for(int j = 0; j < N; ++j){
for(int k = 0; k < HASH_COUNT; ++k){
a[k][i][j] = pow[k][j];
for(int u = 0; u < SZ(LETTERS); ++u) if(LETTERS[u] == s[j][i]){
total[k][u][i] += a[k][i][j];
}
}
}
}
mint NEED[HASH_COUNT];
for(int i = 0; i < N; ++i){
for(int j = 0; j < HASH_COUNT; ++j){
NEED[j] += K * pow[j][i];
}
}
for(int i = 0; i < N; ++i){
mint need[HASH_COUNT];
for(int j = 0; j < HASH_COUNT; ++j){
need[j] = NEED[j] + (M - K) * pow[j][i];
}
for(int j = 0; j < M; ++j){
for(int k = 0; k < HASH_COUNT; ++k){
for(int u = 0; u < SZ(LETTERS); ++u) if(LETTERS[u] == s[i][j]){
need[k] -= total[k][u][j];
}
}
}
bool ok = true;
for(int j = 0; j < HASH_COUNT; ++j){
ok &= need[j] == mint(0);
}
if(ok){
cout << i + 1; exit(0);
}
}
assert(false);
}
