import java.util.Arrays;
import java.util.Scanner;
 
/**
 * ZAKIREN第5章
 *
 * @author K.Yamauchi
 *
 */
public class Main {
 
    /**
     *
     * @param args
     */
    public static void main(String[] args) {
 
        Scanner scan = new Scanner(System.in); // 入力
        int n = Integer.parseInt(scan.nextLine()); // 要素数
 
        // ソート対象配列の読み込み
        String[] targetArrayOrg = scan.nextLine().split(" ");
 
        // 読み込み終了
        scan.close();
 
        // 入力順を保持
        for (int i = 0; i < targetArrayOrg.length; i++) {
            targetArrayOrg[i] += i;
        }
 
        // ソート結果表示用に配列をディープコピー
        String[] targetArrayForBubbleSort = Arrays.copyOf(targetArrayOrg, targetArrayOrg.length);
        String[] targetArrayForSelectionSort = Arrays.copyOf(targetArrayOrg, targetArrayOrg.length);
 
        // バブルソートを実行
        bubbleSort(n, targetArrayForBubbleSort);
 
        // 結果出力
        printSortResult(targetArrayForBubbleSort);
        System.out.println(isStableSort(targetArrayOrg, targetArrayForBubbleSort) ? "Stable" : "Not stable");
 
        // 選択ソートを実行
        selectionSort(n, targetArrayForSelectionSort);
 
        // 結果出力
        printSortResult(targetArrayForSelectionSort);
        System.out.println(isStableSort(targetArrayOrg, targetArrayForSelectionSort) ? "Stable" : "Not stable");
 
    }
 
    /**
     * ソート結果の出力をする。
     * @param sortedArray ソートされた配列
     */
    private static void printSortResult(String[] sortedArray) {
        for (int i = 0; i < sortedArray.length; i++) {
            if (i < sortedArray.length - 1) {
                System.out.print(sortedArray[i].substring(0, 2) + " ");
            } else {
                System.out.println(sortedArray[i].substring(0, 2));
            }
        }
    }
 
    /**
     * 配列に数字の重複があるかを判別する。
     * @param sortedArray ソート済みの配列
     * @return 重複があればtrue、なければfalse
     */
    private static boolean isDuplicate(String[] sortedArray) {
 
        for (int i = 1; i < sortedArray.length; i++) {
            if (sortedArray[i-1].substring(1, 2).equals(sortedArray[i].substring(1, 2))) {
                // ソート済みの配列に置いて、隣り合う数字に同じ数字があれば重複している
                return true;
            }
        }
 
        return false;
    }
 
    /**
     * 安定ソートかを判別する。
     *
     * @param originalArray ソート前のの配列
     * @param sortedArray ソート後の配列
     * @return 安定ソートであればtrue、なければfalse
     */
    private static boolean isStableSort(String[] originalArray, String[] sortedArray) {
 
        // 数字の重複があるとき
        if (isDuplicate(sortedArray)) {
 
            for (int i = 0; i < originalArray.length; i++) {
                for (int j = 1; j < sortedArray.length; j++) {
 
                    // 左隣の数字と一致 かつ 左隣の数字の入力順よりも早かったら安定ソートではない
                    if (originalArray[i].equals(sortedArray[j])
                            && sortedArray[j].substring(1, 2).equals(sortedArray[j-1].substring(1, 2))
                            && Integer.parseInt(sortedArray[j].substring(2, sortedArray[j].length())) < Integer.parseInt(sortedArray[j-1].substring(2, sortedArray[j-1].length()))) {
                        return false;
                    }
                }
            }
        }
 
        return true;
    }
 
    /**
     * 指定された整数配列をバブルソートする。
     *
     * @param n
     *            配列の要素数
     * @param targetArray
     *            バブルソートしたい整数配列
     */
    private static void bubbleSort(int n, String[] targetArray) {
 
        boolean isNotSorted = true; // ソート未完了フラグ
        // ソートが完了するまで
        while (isNotSorted) {
            isNotSorted = false;
 
            // 天秤を右端から移動していく
            for (int i = n - 1; i > 0; i--) {
 
                int nowNumber = Integer.parseInt(targetArray[i].substring(1, 2));
                int leftNumber = Integer.parseInt(targetArray[i - 1].substring(1, 2));
 
                // 自分より小さい値が左側に居たら
                if (nowNumber < leftNumber) {
                    // 2つの要素を入れ替える
                    exchangeArrayValue(targetArray, i, i - 1);
                    isNotSorted = true;
                }
            }
        }
 
    }
 
    /**
     * 指定された整数配列を選択ソートする。
     *
     * @param n
     *            要素数
     * @param targetArray
     *            選択ソートしたい整数配列
     * @return 入れ替え回数
     */
    private static void selectionSort(int n, String[] targetArray) {
 
        for (int i = 0; i < n; i++) {
            int minIndex = i; // 最小値の要素番号
            for (int j = i; j < n; j++) {
 
                int nowNumber = Integer.parseInt(targetArray[j].substring(1, 2));
                int minNumber = Integer.parseInt(targetArray[minIndex].substring(1, 2));
 
                if (nowNumber < minNumber) {
                    // 最小値より低い値があったら最小値の要素番号を更新
                    minIndex = j;
                }
            }
            // 最小値の値と左端を入れ替える
            if (i != minIndex) {
                exchangeArrayValue(targetArray, minIndex, i);
            }
        }
 
    }
 
    /**
     * 配列内の2つの要素を入れ替える。
     *
     * @param array
     *            入れ替えたい要素を含む配列
     * @param a
     *            入れ替えたい要素のindex
     * @param b
     *            入れ替えたい要素のindex
     */
    private static void exchangeArrayValue(Object[] array, int a, int b) {
        Object temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }
 
}


Measured memory_bytes: 26668