import std.stdio;
import std.array;
import std.string;
import std.algorithm;
import std.conv;

void bubbleSort(ref string[] arr) {
  for (auto i = 0; i < arr.length; i++)
    for (auto j = arr.length-1; j >= i+1; j--)
      if (arr[j][1] < arr[j-1][1]) swap(arr[j], arr[j-1]);
}

void selectionSort(ref string[] arr) {
  for (auto i = 0; i < arr.length; i++) {
    int min = i;
    for (auto j = i; j < arr.length; j++)
      if (arr[j][1] < arr[min][1]) min = j;
    swap(arr[i], arr[min]);
  }
}

void main(string[] args)
{
  int n = to!int(strip(readln()));
  string[] arr = split(readln());
  string[] b, s;
  b ~= arr;
  s ~= arr;
  sort!((string a, string b)=>a[1] < b[1], SwapStrategy.stable)(arr);
  bubbleSort(b);
  selectionSort(s);
  writeln(join(b.map!(text), " "));
  writeln(arr == b? "Stable": "Not stable");
  writeln(join(s.map!(text), " "));
  writeln(arr == s? "Stable": "Not stable");
}