#include<stdio.h>
#include<stdlib.h>

typedef struct{
  char Mark;
  int Number;
} Card;

void SelectionSort(Card *,int);
void BubbleSort(Card *,int);
Card Kakunou(char*);

int main() {
  int i,j,k,sum,num;

  scanf("%d",&sum);

  char card[sum][2];
  Card card1[sum],BubleCard[sum],SelectCard[sum];
  for(i=0;i<sum;i++){
    scanf("%s",card[i]);
  }

  for(i=0;i<sum;i++){
    card1[i]=Kakunou(card[i]);
    BubleCard[i]=Kakunou(card[i]);
    SelectCard[i]=Kakunou(card[i]);
  }

  BubbleSort(BubleCard,sum);
  SelectSort(SelectCard,sum);

  return 0;
 
}

Card Kakunou(char A[])
{
  Card card;

  card.Mark = A[0];
  card.Number = atoi(&A[1]);

  return card;
}


void BubbleSort(Card *A,int N)
{
  int i,j,k,s,tmp1;
  char tmp2;
  for(i=0;i<N-1;i++){
    for(j=N-1;j>i+1;j--){
      if(A[j].Number < A[j-1].Number){
	tmp1 = A[j].Number;
	A[j].Number = A[j-1].Number;
	A[j-1].Number = tmp1;

	tmp2 = A[j].Mark;
	A[j].Mark = A[j-1].Mark;
	A[j-1].Mark = tmp2;
      }
    }
  }
}

  

void SelectionSort(Card *A,int N)
{
  int i,j,k,minj,num=0,tmp1;
  char tmp2;

  for(i=0;i<N;i++)
    {
      minj = i;
      for(j=i;j<N;j++)
	{
	  if(A[j].Number < A[minj].Number)
	    {
	      minj = j;
	    }
	}
      if(minj!=i)
	{
	  tmp1 = A[i].Number;
	  A[i].Number = A[minj].Number;
	  A[minj].Number = tmp1;
	 
	  tmp2 = A[j].Mark;
	  A[j].Mark = A[j-1].Mark;
	  A[j-1].Mark = tmp2;
	}
    }
}