//
//  main.cpp
//  Algorithms and Data Structures
//
//  Created by kawauso.
//

#include <iostream>
#include <string>
#include <vector>
#include <cassert>
#include <tuple>

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REPEAT(i, n) FOR(i, 0, n)
#define DECFOR(i, a, b) for (int i = (a); (b) < i; --i)

using namespace std;

bool isStable(std::vector<std::tuple<char, int>> in, std::vector<std::tuple<char, int>> out);

void c_3_5() {
	int n;
	int minj;

	// input
	std::cin >> n;
	std::vector<std::tuple<char, int>> a(n);
	std::vector<std::tuple<char, int>> b(n);
	std::vector<std::tuple<char, int>> c(n);
	REPEAT(i, n) {
		std::string v;
		char v1;
		int v2;

		std::cin >> v;
		const int count = std::sscanf(v.c_str(), "%c%d", &v1, &v2);
		assert(count == 2);
		a[i] = std::make_tuple(v1, v2);
		c[i] = b[i] = a[i];
	}
	assert(a[0] == b[0]);
	// buble sort
	REPEAT(i, n) {
		for (int j = n - 1; j > i; j--) {
			if (std::get<1>(a[j]) >= std::get<1>(a[j - 1])) {
				continue;
			}
			swap(a[j], a[j - 1]);
		}
	}
	// output
	REPEAT(i, a.size()) {
		std::cout << (i == 0 ? "" : " ") << std::get<0>(a[i]) << std::get<1>(a[i]);
	}
	std::cout << std::endl;
	std::cout << (isStable(c, a) ? "Stable" : "Not stable") << std::endl;

	// selection sort
	FOR(i, 0, n) {
		minj = i;
		FOR(j, i + 1, n) {
			if (std::get<1>(b[j]) >= std::get<1>(b[minj])) {
				continue;
			}
			minj = j;
		}
		if (minj == i) {
			continue;
		}
		std::swap(b[i], b[minj]);
	}
	// output
	REPEAT(i, b.size()) {
		std::cout << (i == 0 ? "" : " ") << std::get<0>(b[i]) << std::get<1>(b[i]);
	}
	std::cout << std::endl;
	std::cout << (isStable(c, b) ? "Stable" : "Not stable") << std::endl;
}

bool isStable(std::vector<std::tuple<char, int>> const in, std::vector<std::tuple<char, int>> const out) {
	// combination round-trip
	REPEAT(i, in.size()) {
		FOR(j, i + 1, in.size()) {
			REPEAT(k, out.size()) {
				FOR(l, k + 1, out.size()) {
					if (std::get<1>(in[i]) == std::get<1>(in[j]) && in[i] == out[l] && in[j] == out[k]) {
						// found reverse order
						return false;
					}
				}
			}
		}
	}
	return true;
}

void c_3_4() {
	int n;
	int minj;
	int count;

	cin >> n;
	vector<int> a(n);
	REPEAT(i, n) {
		cin >> a[i];
	}

	count = 0;
	FOR(i, 0, n) {
		minj = i;
		FOR(j, i + 1, n) {
			if (a[j] >= a[minj]) {
				continue;
			}
			minj = j;
		}
		if (minj == i) {
			continue;
		}
		swap(a[i], a[minj]);
		++count;
	}

	REPEAT(k, a.size()) {
		cout << (k ? " " : "") << a[k];
	}
	cout << endl;
	cout << count << endl;
	// 正解との違い: 正解はswapしなくてもいい時もswapしている。比較も初回同じものを比較している。
	// こっちの方がより無駄がない。
}

void c_3_3() {
	int n;
	bool flag;
	int count;

	cin >> n;
	// int price[n];
	vector<int> a(n);
	REPEAT(i, n) {
		cin >> a[i];
	}

	flag = true;
	count = 0;
	for (int i = 0; flag; i++) {
		flag = false;
		DECFOR(j, n - 1, i) {
			if (a[j] >= a[j - 1]) {
				continue;
			}
			const auto v = a[j];
			a[j] = a[j - 1];
			a[j - 1] = v;
			flag = true;
			++count;
		}
	}
	REPEAT(k, a.size()) {
		cout << (k ? " " : "") << a[k];
	}
	cout << endl;
	cout << count << endl;
	// 初解と正解との違い: 交換と非交換を繰り返して出会った一番小さい要素を移動させているという理解が欠如していた
	// よって動作的には正しいが無駄な部分を走査していた
	// swap関数があるのを知らなかった
}

void c_3_2() {
	int n;

	cin >> n;
	// int price[n];
	vector<int> a(n);
	REPEAT(i, n) {
		cin >> a[i];
	}
	REPEAT(k, a.size()) {
		cout << (k ? " " : "") << a[k];
	}
	cout << endl;
	FOR(i, 1, n) {
		int j;

		const auto v = a[i];
		j = i - 1;
		while (j >= 0 and a[j] > v) {
			a[j + 1] = a[j];
			j--;
		}
		a[j + 1] = v;
		REPEAT(k, a.size()) {
			cout << (k ? " " : "") << a[k];
		}
		cout << endl;
	}
	//正解との違い: 特になし
}

void c_2_5() {
	//string s;
	int n;
	cin >> n;
	// int price[n];
	vector<int> price(n);
	REPEAT(i, n) {
		cin >> price[i];
	}
	int maxPrice[n];
	int currentMaxPrice;
	currentMaxPrice = 0;    // or -infinite
	for (int i = n - 1; i >= 0; i--) {
		if (price[i] > currentMaxPrice) {
			currentMaxPrice = price[i];
		}
		maxPrice[i] = currentMaxPrice;
	}
	int maxUp = maxPrice[1] - price[0];
	for (int i = 1; i < n - 1; i++) {
		const int diff = maxPrice[i + 1] - price[i];
		if (diff > maxUp) {
			maxUp = diff;
		}
	}
	cout << maxUp << "\n";
	// 正解との違い: 最大ではなく最小を保持するようにすれば先頭から処理でき、配列を使う必要すらない
	// 競技プログラミングとしてのアドバイス: FOR, REPEATマクロを使いタイプミスをする可能性を減らす
	//   配列の変わりにvectorを用いて宣言以上の領域へのアクセスを検知したりsegmentation faultで落ちるようにする
}

int main(int argc, const char * argv[]) {
	ios::sync_with_stdio(false);
	c_3_5();
	return 0;
}



Measured memory_bytes: 3332