import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.lang.StringBuilder;

/*Question
/?????????????????????????????´?????????????????????????????§?????????????????????(S, H, C, D)??¨???????????°???(1, 2, ..., 9)???????§??????????????¨? 36 ????????????????????¨????????????????????°??????????????? 8 ???"H8"??????????????? 1 ???"D1"??¨??¨????????????
????????????????????????????????????????????¢?????´??????????????¨???????????????????????? N ????????????????????????????????°??????????????????????????´?????????????????°????????????????????????????????????
/??¢?????´??????????????????????????\????????????????????????????????????????????¨??????????????°??????????´???? 0 ??????????????§?¨???°?????????????????????
/1 BubbleSort(C, N)
/2 for i = 0 to N-1
/3 for j = N-1 downto i+1
/4 if C[j].value < C[j-1].value
/5 C[j] ??¨ C[j-1] ?????????
/6
/7 SelectionSort(C, N)
/8 for i = 0 to N-1
/9 minj = i
/10 for j = i to N-1
/11 if C[j].value < C[minj].value
/12 minj = j
/13 C[i] ??¨ C[minj] ?????????
/??????????????¢?????´?????????????????????????????????????????\??????????????????????????????????????£??????????????±????????????????????????
/????????§??????????????°?????????????????????????????°????????´?????????????????\??????????????????????????§????????????????????¨?????????????????????????????¨?????¶?????¨???????????????
/??????????????????????????????????????????????????¢?????´????????????????????????????????¢?????´???????????¨?¨???????????????? 
*/

/*Input
/1 ??????????????????????????° N ???????????????????????? 2 ????????? N ???????????????????????????????????????
/???????????????????????¨??°???????????¢?????¨??????????????§???????????£???????????????????????????????????§??????????????????????????? 
*/

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
		//????????¨
		StringBuffer br = new StringBuffer();
		/*??\???
		/??????????´???°?????\???????¬??????????????????\???
		*/
		int n = Integer.parseInt(sc.readLine());
		String[] ca = sc.readLine().split(" ");
		//????????¨-??????????????¨
		String[] k = new String[n];
		/*??°??????Selection??¨Bubble???????????????
		/?????£??????????????????????????????
		/isStable????????????????????????????????????????????????????????? (isStable?????????????????§???????????????)
		*/
		k = Bubble(ca);
		for (String s:k)
			br.append(s+" ");
		br.deleteCharAt(br.lastIndexOf(" "));
		br.append("\n");
		br.append("Stable\n");
		k = Selection(ca);
		for (String s:k)
			br.append(s+" ");
		br.deleteCharAt(br.lastIndexOf(" "));
		br.append("\n");
		br.append(isStable(ca,k)+"\n");
		System.out.print(br);
	}

	/*Selection????????????
	/?????????????????????????????????
	/?????????????????????????????????????????????????????°??¨??????????????????????±?????°????????????°????????????????¨???¶??????
	/??¨???????????´???????????°??¨????????????????¨???¶?????????????????????????????¨??\????????????
	/@return int
	*/

	public static String[] Selection(String[] a) {
		//????????¨-????????????????????£??????????????????????????????????????????
		String[] syu = new String[a.length];
		for (int i = 0;i < a.length;i++)
			syu[i] = a[i];
		//????????????????????????????????\????????¨
		String s;
		//????????????????????????????????\????????¨
		int min;
		for (int i = 0;i < syu.length;i++) {
			min = i;
			for (int j = i + 1;j < syu.length;j++) {
				if (syu[j].charAt(1) < syu[min].charAt(1)) min = j;
			}
			if (min != i){
				s = syu[i];
				syu[i] = syu[min];
				syu[min] = s;
			}
		}
		return syu;
	}

	/*Bubble????????????
	/????????????????????????????????????
	/???????????¨?????????????°????????????°??????
	/@return int
	*/

	public static String[] Bubble(String[] a) {
		//????????¨-????????????????????£????????????????????????????????????
		String[] syu = new String[a.length];
		for (int i = 0;i < a.length;i++)
			syu[i] = a[i];
		//????????????????????????????????\????????¨
		String s;
		for (int i = 0;i < syu.length;i++) {
			for (int j = syu.length-1;j > i;j--) {
				if (syu[j].charAt(1) < syu[j-1].charAt(1)){
					s = syu[j];
					syu[j] = syu[j-1];
					syu[j-1] = s;
				}
			}
		}
		return syu;
	}

	/*isStable????????????
	/????????§?????¨???????????§???????????°?????§?????????????????\
	/??\?????¨????§?????????????????????????????????????
	/@return String
	*/
	static String isStable(String[] ca,String[] k){
		for (int i = 0;i < k.length-1;i++) {
			int a = 0;
			int b = 0;
			if (k[i].charAt(1) == k[i+1].charAt(1)) {
				for (int j = 0;j < ca.length;j++) {
					if (ca[j].equals(k[i])) a = j;
					else if (ca[j].equals(k[i+1])) b = j;
				}
				if (b - a < 0) return "Not stable";
			}
		}
		return "Stable";
	}
}

Measured memory_bytes: 24352