#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int n, m;
struct solver{
    int cnt, value;
    char str[55];
    void input(int i){
        this->cnt = i;
        scanf("%s", str);
        build();
    }
    // 逆序数
    void build() {
        int A , T , C , G;
        A = T = C = G = 0;
        int ans = 0;
        for(int i = 0 ; i < n ; i++) {
            if (str[i] == 'A') A ++ , ans += C + G + T;
            if (str[i] == 'C') C ++ , ans += G + T;
            if (str[i] == 'G') G ++ , ans += T;
            if (str[i] == 'T') T ++;
        }
        value = ans;
    }
    void output(){
        printf("%s\n", str);
    }
    bool operator < (const solver & rht) const {
        if(this->value == rht.value) return this->cnt < rht.cnt;
        return this->value < rht.value;
    }
};
solver key[110];
int main() {
    while(~scanf("%d%d", &n, &m)) {
        for(int i = 0 ;i < m ; i++) key[i].input(i);
        sort(key, key + m);
        for(int i = 0 ;i < m ; i++) key[i].output();
    }
    return 0;
}