#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>
#include <math.h>

#define BOOL int
#define TRUE 0
#define FALSE 1


#define DT_MAX (36+4)
#define S_	   (0x01)
#define H_	   (0x02)
#define C_	   (0x04)
#define D_	   (0x08)

typedef struct {
	char kind;
	char wk[3];
	int	 data;
} CARD_T;

typedef struct {
	char kind[4];
	char num;
	char dmy[3];
} CARD_NUM_T;

char chg(int type, char kind)
{
	if (type == 0) {
		switch(kind) {
		case 'S':
			return S_;
		case 'H':
			return H_;
		case 'C':
			return C_;
		default:
			return D_;
		}
	}
	else {
		switch(kind) {
		case S_:
			return 'S';
		case H_:
			return 'H';
		case C_:
			return 'C';
		default:
			return 'D';
		}
	}
}


void prt(CARD_T *cd_p,int n,BOOL state_mch)
{
	int i;
	char wk;
	for (i=0 ; i<n ; i++) {
		wk = chg(1,cd_p[i].kind);
		printf("%c%d",wk,cd_p[i].data);
		if (i != n-1) {
			printf(" ");
		}
	}
	printf("\n");
	if (state_mch == TRUE) {
		printf("Stable\n");
	}
	else {
		printf("Not stable\n");
	}
}

BOOL chk(int n,CARD_T *cd_p,CARD_NUM_T *cnt_p)
{
	int i,j;
	int wk[10];
	int match;

	memset(wk,'\0',sizeof(wk));
	for (i=0 ; i<n ; i++) {
		if (cnt_p[i].num < 2) {
			continue;
		}

		/*--- num >= 2 ---*/
		for(match=0,j=0 ; j<n ; j++) {
//			if (cd_p[j].data == cnt_p[i].num) {
			if (cd_p[j].data == i) {
//					if (cd_p[j].data != i) {
//						continue;
//					}
				if (cd_p[j].kind != cnt_p[i].kind[match]) {
					return FALSE;
				}
				match++;
				if (cnt_p[i].num == match) {
					break;
				}
			}
		}
	}
	return TRUE;
}

void bable_sort(CARD_T *cd_p,int n)
{
	int i;
	int j,flg;
	int wk;
	int wk_kind;


	for (flg=1,j=0 ; flg!=0 ; j++) {
		flg = 0;
		for(i=0 ; i<n-1 ; i++) {
			if (cd_p[i].data>cd_p[i+1].data) {
				flg++;
				wk = cd_p[i+1].data;
				wk_kind=cd_p[i+1].kind;
				cd_p[i+1].data = cd_p[i].data;
				cd_p[i+1].kind = cd_p[i].kind;
				cd_p[i].data   = wk;
				cd_p[i].kind   = wk_kind;
			}
		}
	}
}

void selec_sort(CARD_T *cd_p,int n)
{
	int minj;
	int chg_cnt;
	int i;
	int j;
	int wk;
	int wk_kind;
	int flg;

	for (chg_cnt=0,i=0 ; i<n ; i++) {
		minj=i;
		for (flg=0,j=i+1 ; j<n ; j++) {
			if (cd_p[j].data < cd_p[minj].data) {
				minj = j;
				flg++;
			}
		}
		if (flg != 0) {
			chg_cnt++;
			wk = cd_p[minj].data;
			wk_kind=cd_p[minj].kind;
			cd_p[minj].data = cd_p[i].data;
			cd_p[minj].kind = cd_p[i].kind;
			cd_p[i].data=wk;
			cd_p[i].kind=wk_kind;
		}
	}
}
int main()
{
	int n,wk,i,flg,j;
	CARD_T card_in[DT_MAX],card_cpy[DT_MAX];
	int chg_cnt;
	BOOL state_mch;
	CARD_NUM_T  cnt[10];
	char buff[8192];
	char *ptr,*wk_p;
	char mark;

	memset(cnt,'\0',sizeof(cnt));
	gets(buff);
	sscanf(buff,"%d",&n);
	gets(buff);
	
	ptr = strtok(buff," ");
	for (i=0 ; i<n ; i++) {
//		sscanf_s(ptr,"%s",&mark,&(card_in[i].data));
		mark = ptr[0];
		sscanf(ptr+1,"%d");
		
		card_in[i].kind = chg(0,mark);
		cnt[card_in[i].data].kind[cnt[card_in[i].data].num] = card_in[i].kind;
		cnt[card_in[i].data].num++;
		ptr = strtok(NULL," ");
	}

	/*-- DISP --*/
	memcpy(card_cpy,card_in,sizeof(card_cpy));
	for (i=0 ; i<2 ; i++) {
		switch(i) {
		case 0:
			bable_sort(card_in,n);
			state_mch=chk(n,card_in,cnt);
			prt(card_in,n,state_mch);
			break;
		default:
			selec_sort(card_cpy,n);
			state_mch=chk(n,card_cpy,cnt);
			prt(card_cpy,n,state_mch);
			break;
		}
		
	}
	return 0;
}