def bubble_sort(A, n):

	flag = 1

	i = 0



	while flag:

		flag = 0

		for j in range(n-1, i, -1):

			if int(A[j][1]) < int(A[j-1][1]):

				A[j], A[j-1] = A[j-1], A[j]

				flag = 1



		i += 1

	

	return A



def selection_sort(A, n):

	for i in range(n-1):

		minj = i

		for j in range(i, n):

			if int(A[j][1]) < int(A[minj][1]):

				minj = j



		if i != minj:

			A[i], A[minj] = A[minj], A[i]



	return A



def is_stable(A, B, n):

	for i in range(0, n):

		for j in range(i+1, n):

			for a in range(0, n):

				for b in range(a+1, n):

					if int(A[i][1]) == int(A[j][1]) and A[i] == B[b] and A[j] == B[a]:

						return False



	return True



def print_stable(flag):

	if flag:

		print('Stable')

	else:

		print('Not stable')



if __name__ == '__main__':

	n = int(eval(input()))

	A = list(input().split())

	A2 = A[:]



	B = bubble_sort(A, n)

	print((' '.join(B)))

	print_stable(is_stable(A, B, n))



	B = selection_sort(A2, n)

	print((' '.join(B)))

	print_stable(is_stable(A, B, n))
def bubble_sort(A, n):

	for i in range(n):

		for j in range(n-1, i, -1):

			if A[j][1] < A[j-1][1]:

				A[j], A[j-1] = A[j-1], A[j]



	print((' '.join(A)))



def selection_sort(A, n):

	for i in range(n):

		minj = i

		for j in range(i, n):

			if A[j][1] < A[minj][1]:

				minj = j

		if i != minj:

			A[i], A[minj] = A[minj], A[i]



	print((' '.join(A)))



if __name__ == '__main__':

	n = int(eval(input()))

	A = list(input().split())

	B = A[:]



	bubble_sort(A, n)

	print('Stable')



	selection_sort(B, n)

	print(('Stable' if A == B else 'Not stable'))
def bubble_sort(A, n):
    flag = 1
    i = 0
    while flag:
        flag = 0
        for j in range(n - 1, i, -1):
            if int(A[j][1]) < int(A[j - 1][1]):
                A[j], A[j - 1] = A[j - 1], A[j]
                flag = 1
        i += 1
    return A


def selection_sort(A, n):
    for i in range(n - 1):
        minj = i
        for j in range(i, n):
            if int(A[j][1]) < int(A[minj][1]):
                minj = j
        if i != minj:
            A[i], A[minj] = A[minj], A[i]
    return A


def is_stable(A, B, n):
    for i in range(0, n):
        for j in range(i + 1, n):
            for a in range(0, n):
                for b in range(a + 1, n):
                    if int(A[i][1]) == int(A[j][1]) and A[i] == B[b] and A[j] == B[a]:
                        return False
    return True


def print_stable(flag):
    if flag:
        print("Stable")
    else:
        print("Not stable")


if __name__ == "__main__":
    n = int(eval(input()))
    A = list(input().split())
    A2 = A[:]
    B = bubble_sort(A, n)
    print((" ".join(B)))
    print_stable(is_stable(A, B, n))
    B = selection_sort(A2, n)
    print((" ".join(B)))
    print_stable(is_stable(A, B, n))

def bubble_sort(A, n):
    for i in range(n):
        for j in range(n - 1, i, -1):
            if A[j][1] < A[j - 1][1]:
                A[j], A[j - 1] = A[j - 1], A[j]
    print((" ".join(A)))


def selection_sort(A, n):
    for i in range(n):
        minj = i
        for j in range(i, n):
            if A[j][1] < A[minj][1]:
                minj = j
        if i != minj:
            A[i], A[minj] = A[minj], A[i]
    print((" ".join(A)))


if __name__ == "__main__":
    n = int(eval(input()))
    A = list(input().split())
    B = A[:]
    bubble_sort(A, n)
    print("Stable")
    selection_sort(B, n)
    print(("Stable" if A == B else "Not stable"))

-    flag = 1 -    i = 0 -    while flag: -        flag = 0 +    for i in range(n): -            if int(A[j][1]) < int(A[j - 1][1]): +            if A[j][1] < A[j - 1][1]: -                flag = 1 -        i += 1 -    return A +    print((" ".join(A))) -    for i in range(n - 1): +    for i in range(n): -            if int(A[j][1]) < int(A[minj][1]): +            if A[j][1] < A[minj][1]: -    return A - - -def is_stable(A, B, n): -    for i in range(0, n): -        for j in range(i + 1, n): -            for a in range(0, n): -                for b in range(a + 1, n): -                    if int(A[i][1]) == int(A[j][1]) and A[i] == B[b] and A[j] == B[a]: -                        return False -    return True - - -def print_stable(flag): -    if flag: -        print("Stable") -    else: -        print("Not stable") +    print((" ".join(A))) -    A2 = A[:] -    B = bubble_sort(A, n) -    print((" ".join(B))) -    print_stable(is_stable(A, B, n)) -    B = selection_sort(A2, n) -    print((" ".join(B))) -    print_stable(is_stable(A, B, n)) +    B = A[:] +    bubble_sort(A, n) +    print("Stable") +    selection_sort(B, n) +    print(("Stable" if A == B else "Not stable"))