#include <iostream>
using namespace std;

struct DNA
{
    char DNA_string[110];
    int sortqual;
};    

DNA _DNA[50];
int n,m;

void work()
{
    int temp,temp_pos;int i,j;
    for(i=0;i<n;i++)
    {
        temp=10000000;
        for(j=0;j<n;j++)
        {
            if (_DNA[j].sortqual<temp)
            {
                temp=_DNA[j].sortqual;
                temp_pos=j;
            }    
        }    
        cout<<_DNA[temp_pos].DNA_string<<endl;
        _DNA[temp_pos].sortqual=10000001;
    }    
    
}    

int main()
{
    while(cin>>m>>n)
    {
        int a,c,t,g;
        int opp_sort;
        for(int i=0;i<n;i++)
        {
            cin>>_DNA[i].DNA_string;
            a=c=t=g=opp_sort=0;
            for(int j=(m-1);j>=0;j--)
            {
                switch(_DNA[i].DNA_string[j])
                {
                    case 'A':a++;break;
                    case 'C':c++;opp_sort+=a;break;
                    case 'G':g++;opp_sort+=(a+c);break;
                    case 'T':t++;opp_sort+=(a+c+g);break;
                }    
            }    
            _DNA[i].sortqual=opp_sort;
        }    
        work();
    }    
    return 0;
}