#include <stdio.h>

#define MaxN 1000
#define MaxF 10000

int N, F; // počet disků a fotografií
char S[MaxF][MaxN]; // všechny fotografie
int I[MaxF]; // pole odkazů na fotografie, které bude přeuspořádáno

void prohod(int * a, int * b) {
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

// Uspořádej fotografie I[l], I[l+1], ..., I[r-1]
// Předpokládá se, že aktuálním úkolem je přesunout disky 1 až k z výchozí tyče
// na cílovou tyč
void usporadej(int k, int l, int r, char vychozi, char cilova, char pomocna) {
	if (k == 0) return;
	if (r - l <= 1) return;
	// Fotografie přeuspořádáme tak, aby ty, na kterých je disk k na výchozí tyči,
	// předcházely ty, na kterých je tento disk již na cílové tyči
	int hranice = l;
	for (int i = l; i < r; i++) {
		if (S[I[i]][k-1] == vychozi) {
			prohod(&I[i], &I[hranice]);
			hranice++;
		}
	}
	usporadej(k-1, l, hranice, vychozi, pomocna, cilova);
	usporadej(k-1, hranice, r, pomocna, cilova, vychozi);
}

int main(void) {
	scanf("%d%d", &N, &F);
	for (int f = 0; f < F; f++) {
		I[f] = f;
		scanf(" %s", S[f]);
	}

	usporadej(N, 0, F, 'A', 'B', 'C');

	for (int f = 0; f < F; f++)
		printf("%s\n", S[I[f]]);

	return 0;
}