import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws Exception {
        // ??\????????°?????????
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // ?????°????¨????
        int cnt = Integer.parseInt(br.readLine());
        // ????????????
        String[] sarray = br.readLine().split(" ",cnt);
        
        // ???????????????????????????
        //String[] bsortarray = bubbleSort(sarray,cnt);
        String b_sarray[] = bubbleSort(sarray,cnt);
        // ????????§?????????
        isStable(b_sarray,b_sarray);
        // ????????????????????????
        String[] s_sarray = selectionSort(sarray,cnt);
        // ????????§?????????
        isStable(b_sarray,s_sarray);
    }
    
    // ???????????????
    public static String[] selectionSort(String[] sarray, int cnt){
        // ??????????????????
        //String[] s_sarray = Arrays.copyOf(sarray,sarray.length);
        String[] s_sarray = sarray.clone();
        int chgNum = 0;
        // ???????????????????????????
        for(int i = 0; i < cnt; i++){
            // ????°????????????????
            int minj = i;
            // ?????????????????§??????
            for(int j = i; j < cnt; j++){
                if(intValue(s_sarray[j]) < intValue(s_sarray[minj])){
                    minj = j;
                }
            }
            // ????°?????????\?????????
            if(minj != i){
                String v = s_sarray[i];
                s_sarray[i] = s_sarray[minj];
                s_sarray[minj] = v;
                chgNum = chgNum + 1;
            }
        }
        outPrint(s_sarray,cnt);
        //System.out.println(chgNum);
        return s_sarray;
    }
    
    // ??????????????????
    public static String[] bubbleSort(String[] sarray , int length) {
        // ??????????????????
        //String[] b_array = Arrays.copyOf(sarray,sarray.length);
        String[] b_array = sarray.clone();
        //????????????????????????
        for (int i = 0; i < length -1 ; i++){
            for(int j = length - 1; j > i; j--){
                if(intValue(b_array[j]) < intValue(b_array[j - 1])){
                    String v = b_array[j];
                    b_array[j] = b_array[j - 1];
                    b_array[j - 1] = v;
                }
            }
        }
        // ??????????????????
        outPrint(b_array,length);
        
        return b_array;
    }

    // ??????????????????
    public static void outPrint(String[] sarray, int cnt){
        StringBuilder sb = new StringBuilder();
        for(int n = 0; n < cnt ; n++){
            if(n>0)sb.append(" ");
            sb.append(sarray[n]);
        } 
        System.out.println(sb);
        sb.setLength(0);
    }

    // ??????????????????
    public static int intValue(String str){
        int value = Integer.parseInt(str.substring(1,2));
        return value;
    }

    // ??????????????????
    public static void isStable(String[] array1, String[] array2){
        if(Arrays.equals(array1,array2)){
            System.out.println("Stable");
        } else {
            System.out.println("Not stable");
        }
    }
};


Measured memory_bytes: 24700