#include<cstdio>
int main() {
	int n, i, j, minj;
	char c[36][3], d[36][3], tmp;
	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		scanf("%s", c[i]);
		for (j = 0; j < 3; j++)d[i][j] = c[i][j];
	}
	for (i = 0; i < n; i++) {
		for (j = n - 1; j > i; j--) {
			if (c[j][1] < c[j - 1][1]) {
				tmp = c[j][0];
				c[j][0] = c[j - 1][0];
				c[j - 1][0] = tmp;
				tmp = c[j][1];
				c[j][1] = c[j - 1][1];
				c[j - 1][1] = tmp;
			}
		}
	}
	printf("%s", c[0]);
	for (i = 1; i < n; i++)printf(" %s", c[i]);
	printf("\nStable\n");
	for (i = 0; i < n; i++) {
		minj = i;
		for (j = i; j < n; j++) {
			if (d[j][1] < d[minj][1])minj = j;
		}
		tmp = d[i][0];
		d[i][0] = d[minj][0];
		d[minj][0] = tmp;
		tmp = d[i][1];
		d[i][1] = d[minj][1];
		d[minj][1] = tmp;
	}
	printf("%s", d[0]);
	for (i = 1; i < n; i++)printf(" %s", d[i]);
	for (i = 0; i < n; i++) {
		for (j = 0; j < 2; j++) {
			if (c[i][j] != d[i][j]) {
				printf("\nNot stable\n");
				return 0;
			}
		}
	}
	printf("\nStable\n");
	return 0;
}
