#include<bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define vvi vector<vi>
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
int MAP[4] = { 'A', 'C', 'G', 'T' };
struct genom {
int idx = -1;
vi gen;
void readGen(int i) {
idx = i;
string s;
cin >> s;
int M = sz(s);
gen.resize(M);
for (int j = 0; j < M; ++j) {
if (s[j] == 'A') gen[j] = 0;
else if (s[j] == 'C') gen[j] = 1;
else if (s[j] == 'G') gen[j] = 2;
else gen[j] = 3;
}
}
void print() {
for (int i : gen) cout << (char) MAP[i];
cout << "\n";
}
};
int compare(genom & g1, genom & g2) {
int diff = 0;
for (int i = 0; i < sz(g1.gen); ++i) {
diff += (int) (g1.gen[i] != g2.gen[i]);
}
return diff;
}
void ReducePairs(vector<genom> & base, vector<genom> & raus, int K) {
vector<genom> candidates;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
shuffle(all(base), rng);
int c = sz(candidates), r = sz(raus);
while (sz(base) > 1) {
int l1 = sz(base) - 1;
int l2 = l1 - 1;
if (compare(base[l1], base[l2]) == K) {
candidates.emplace_back();
candidates.emplace_back();
swap(base[l1], candidates[c++]);
swap(base[l2], candidates[c++]);
} else {
raus.emplace_back();
raus.emplace_back();
swap(raus[r++], base[l1]);
swap(raus[r++], base[l2]);
}
base.pop_back();
base.pop_back();
}
if (sz(base) == 1) {
candidates.emplace_back();
swap(base[0], candidates[c++]);
base.pop_back();
}
swap(base, candidates);
}
void ReduceCount(vector<genom> & base, vector<genom> & raus, int K) {
vector<genom> candidates;
int c = 0, r = sz(raus);
int N = sz(base);
int M = sz(base[0].gen);
vvi cnts(M, vi(4, 0));
for (int j = 0; j < N; ++j) {
for (int i = 0; i < M; ++i) ++cnts[i][base[j].gen[i]];
}
int ziel = M * N - (N - 1) * K;
for (int j = N-1; j >= 0; --j) {
int sum = 0;
for (int i = 0; i < M; ++i) sum += cnts[i][base[j].gen[i]];
if (sum == ziel) {
candidates.emplace_back();
swap(base[j], candidates[c++]);
} else {
raus.emplace_back();
swap(base[j], raus[r++]);
}
}
swap(base, candidates);
}
void ReduceRest(vector<genom> & base, vector<genom> & raus, int K) {
vector<genom> candidates;
int c = 0, r = sz(raus);
for (int j = sz(base)-1; j >= 0; --j) {
bool poss = true;
for (genom g : raus) {
if (compare(base[j], g) != K) { poss = false; break; }
}
if (poss) {
for (int k = 0; k < j; ++k) {
if (compare(base[k], base[j]) != K) { poss = false; break; }
}
}
if (poss) {
candidates.emplace_back();
swap(base[j], candidates[c++]);
} else {
raus.emplace_back();
swap(base[j], raus[r++]);
}
base.pop_back();
}
swap(base, candidates);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int N, M, K;
scanf("%d %d %d", & N, & M, & K);
vector<genom> gens(N);
for (int i = 0; i < N; ++i) {
gens[i].readGen(i);
}
cout << "read Input completed\n";
vector<genom> raus;
ReduceCount(gens, raus, K);
cout << "Count\n";
// for (genom g : gens) g.print();
int altsize = sz(gens) + 1;
while (altsize > sz(gens)) {
altsize = sz(gens);
ReducePairs(gens, raus, K);
}
cout << "Pairs\n";
// for (genom g : gens) g.print();
ReduceRest(gens, raus, K);
cout << "Rest\n";
for (genom g : gens) cout << g.idx+1 << endl;
}
