#include<iostream>
#include<algorithm>
using namespace std;
struct Str{
    char s[55];
    int num;  //逆序数个数
};

void BubbleSort(Str r[],int n) //冒泡排序
{
  	int i,j;
	Str temp;
  	bool flag;
  	i=n-1;
  	flag=true;
  	while(i>0&&flag)
    {
        flag=false;
        for(j=0;j<i;j++) //进行一趟排序
            if(r[j].num>r[j+1].num)
            {
                flag=true;
                temp=r[j]; //交换两个记录
                r[j]=r[j+1];
                r[j+1]=temp;
            }
        i--;
    }
}

int main()
{
    int n,m,i,j;
    Str str[105];
    while(cin>>n>>m)
	{
        for(i=0;i<m;i++)//输入
            cin>>str[i].s;
        for(i=0;i<m;i++)
		{
            int sum=0;
            int A=0,C=0,G=0;
            for(j=n-1;j>=0;j--)
			{
                switch(str[i].s[j])//计算逆序数
				{    
                    case 'A':A++;break;
                    case 'C':C++;sum+=A;break;
                    case 'G':G++;sum+=A;sum+=C;break;
                    case 'T':sum+=A;sum+=C;sum+=G;break;
                    default:break;
                }
            }
            str[i].num=sum;
        }
        BubbleSort(str,m);//冒泡排序是稳定排序
        for(i=0;i<m;i++)
            cout<<str[i].s<<endl;
    }
    return 0;
}