import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = ip(br.readLine());
        Card[] list = new Card[n];
        String[] lines = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            char[] c = lines[i].toCharArray();
            list[i] = new Card(c[0], c[1] - '0');
        }
        Card[] s1 = bubbleSort(list.clone(), n);

        Card[] s2 = selectionSort(list.clone(), n);
        checkStable(s1, s2);
    }

    static void checkStable(Card[] list1, Card[] list2) {
        for (int i = 0; i < list1.length; i++) {
            if (list1[i].serialN != list2[i].serialN) {
                System.out.println("Not stable");
                return;
            }
        }
        System.out.println("Stable");
    }

    static Card[] selectionSort(Card[] list, int n) {
        for (int i = 0; i < n; i++) {
            int minj = i;
            for (int j = i + 1; j < n; j++) {
                if (list[j].rank < list[minj].rank) {
                    minj = j;
                }
            }
            if (i != minj) {
                swap(list, i, minj);
            }
        }
        print(list);
        return list;
    }

    static Card[] bubbleSort(Card[] list, int n) {
        boolean flag = true;
        while (flag) {
            flag = false;
            for (int i = n - 1; i > 0; i--) {
                if (list[i].rank < list[i - 1].rank) {
                    swap(list, i, i - 1);
                    flag = true;
                }
            }
        }
        print(list);
        System.out.println("Stable");
        return list;
    }

    private static void print(Card[] list) {
        int n = list.length;
        for (int i = 0; i < n; i++) {
            System.out.print(list[i].suit + "" + list[i].rank);
            if (i < n - 1) {
                System.out.print(" ");
            }
        }
        System.out.println();
    }

    static void swap(Card[] list, int a, int b) {
        Card temp = list[a];
        list[a] = list[b];
        list[b] = temp;
    }

    static void swap(int[] list, int a, int b) {
        int temp = list[a];
        list[a] = list[b];
        list[b] = temp;
    }

    static int[] createListInt(String line) {
        String[] lines = line.split(" ");
        int n = lines.length;
        int[] list = new int[n];
        while (n-- > 0) {
            list[n] = Integer.parseInt(lines[n]);
        }
        return list;
    }

    static long[] createListLong(String line) {
        String[] lines = line.split(" ");
        int n = lines.length;
        long[] list = new long[n];
        while (n-- > 0) {
            list[n] = Long.parseLong(lines[n]);
        }
        return list;
    }

    static int ip(String s) {
        return Integer.parseInt(s);
    }

    static long lp(String s) {
        return Long.parseLong(s);
    }
}

class Card {
    static int n = 0;
    int serialN;
    char suit;
    int rank;

    Card(char suit, int rank) {
        serialN = n++;
        this.suit = suit;
        this.rank = rank;
    }

}

Measured memory_bytes: 24404