#include<iostream.h>

int n=0,m=0;//m:giving the number of strings
		//n:giving the length of the strings


void input(char *array[])//input and compute the "unsortedness" at the same
{

	int i,j,k;
	int  time=0;
	for(i=0;i<m;i++)
	{
		array[i]=new char[n+1];
		time=0;
		for(j=0;j<n;j++)
		{
			cin>>array[i][j]; 
			for(k=0;k<j;k++)//65A 67C 71G 84T
				if(array[i][k]<array[i][j])//INPUT DATA AND COMPUTE
					time++;
		}
		 array[i][n]=time;
		 
	}
}

void process(char * array[])//arrange the strings 
{
	int i,j;
	char * p=NULL;
	int mark=0;
	char temp;
	for(i=0;i<m;i++)
	{
		mark=i;
		temp=array[i][n];
		for(j=i+1;j<m;j++)
		{
			if(temp<array[j][n])//inversions bigger 
			{
				temp=array[j][n];//record the point (array[j])
				mark=j;
			}	
		}
		if(mark!=i)
		{
			p=array[i];
			array[i]=array[mark];
			array[mark]=p;				 
		}	
	}
}

void output(char * array[])
{
	int i,j;
	for(i=0;i<m;i++)
	{
		for(j=0;j<n;j++)
			cout<<array[i][j];
		cout<<(int)array[i][n];
		 delete[] array[i];
		cout<<endl;

	}

}
void  main()
{
	//char * array[100];
	char ** array;	
	cin>>n>>m;
	array=new  char* [m];
 
	input(array);
	
	process(array);

 	output(array);
}