#include<stdio.h>
static const int N=36;
typedef struct{
  char mark;
  int atai;
}CARD;
void BubbleSort(CARD *,int);
void Selectionsort(CARD *,int);

void Swap(card *a,card *y){
  card temp;
  temp=*a;
  *a=*b;
  *b=temp;
}
int main(){
  CARD c[N];
  int i,n,judge1,judge2;
  scanf("%d",&n);
  for(i=0;i<n;i++)scanf("%c%d",c[i].mark,c[i].atai);
  BubbleSort(&c, n);
  Selectionsort(&c,n);
  judge1=isStable(c,)

  return 0;
}

void BubbleSort(CARD c,int n){
  int i,j;
  CARD key;
  for(i=0;i<n;i++)
    {
      for(j=n-1;j>i+1;j--)
	{
	  if(c[j].atai<c[j-1].atai)
	    {
	      key=c[j];
	      c[j]=c[j-1];
	      c[j-1]=key;
	    }
	}
    }
  for(i=0;i<n-1;i++)printf("%c%d ",c[i].mark,c[i].atai);
  printf("%c%d\n",c[i].mark,c[i].atai);
  isStable(char *in,char *out);
  //stable????????????
}
void Selectionsort(CARD c,int n){
  int i,j,miji;
  CARD key;
  for(i=0;i<n;i++)
    {
      miji=i;
      for(j=i;j>n-1;j--)
	{
	  if(c[j].atai<c[miji].atai)minj=j;
	} 
      key=c[i];
      c[i]=c[miji];
      c[miji]=key;
    }
  for(i=0;i<n-1;i++)printf("%c%d ",c[i].mark,c[i].atai);
  printf("%c%d\n",c[i].mark,c[i].atai);
  isStable(in,out);
   //stable????????????
}
void isStable(char *in,char *out, int n){
  int i,j,a,b;
  for(i=0;i<n;i++)
    {
      for(j=i+1;j<n;j++)
	{
	  for(a=0;a<n;a++)
	    {
	      for(b=a+1;b<n;b++)
		{
		  if(in[i].atai==in[j].atai&&in[i]==out[b]&&in[j]==out[a])return -1;
		}
	    }
	}
    }
  return 0;
}