def bubble_sort(r, n):

    flag = True  # ??£??\????´?????????¨????????°

    while flag:

        flag = False

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

            if r[i - 1][1] > r[i][1]:

                r[i - 1], r[i] = r[i], r[i - 1]

                flag = True

    return r





def select_sort(r, n):

    for i in range(0, n):

        minj = i

        for j in range(i, n):

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

                minj = j

        if i != minj:

            r[i], r[minj] = r[minj], r[i]

    return r





def stable_sort(r, sort_r):

    for i in range(len(r)):

        for j in range(i + 1, len(r)):

            for a in range(len(sort_r)):

                for b in range(a + 1, len(sort_r)):

                    if r[i][1] == r[j][1] and r[i] == sort_r[b] and r[j] == sort_r[a]:

                         return "Not stable"



    return "Stable"





N = int(eval(input()))

R = list(input().split())

C = R[:]

BS_R = bubble_sort(R, N)

SS_R = select_sort(C, N)

print((*BS_R))

print((stable_sort(R, BS_R)))

print((*SS_R))

print((stable_sort(R, SS_R)))
def selectionSort(n, A):

    cnt = 0

    for i in range(n):

        minj = i

        for j in range(i, n):

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

                minj = j

        if i != minj:

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

            cnt += 1

    return A





def bubbleSort(n, A):

    flag = True

    cnt = 0

    while flag:

        flag = False

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

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

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

                cnt += 1

                flag = True

    return A





def stableSort(input, output):

    n = len(input)

    for i in range(n):

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

            for a in range(n):

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

                    if input[i][1] == input[j][1] and input[i] == output[b] and input[j] == output[a]:

                        return print("Not stable")

    return print("Stable")





if __name__ == '__main__':

    n = int(input())

    R = list(map(str, input().split()))

    C = R[:]

    D = R[:]  #????????¨?????????

    SR = selectionSort(n, R)

    BR = bubbleSort(n, C)

    print(*BR)

    stableSort(D,BR)

    print(*SR)

    stableSort(D,SR)

def bubble_sort(r, n):
    flag = True  # ??£??\????´?????????¨????????°
    while flag:
        flag = False
        for i in range(n - 1, 0, -1):
            if r[i - 1][1] > r[i][1]:
                r[i - 1], r[i] = r[i], r[i - 1]
                flag = True
    return r


def select_sort(r, n):
    for i in range(0, n):
        minj = i
        for j in range(i, n):
            if r[j][1] < r[minj][1]:
                minj = j
        if i != minj:
            r[i], r[minj] = r[minj], r[i]
    return r


def stable_sort(r, sort_r):
    for i in range(len(r)):
        for j in range(i + 1, len(r)):
            for a in range(len(sort_r)):
                for b in range(a + 1, len(sort_r)):
                    if r[i][1] == r[j][1] and r[i] == sort_r[b] and r[j] == sort_r[a]:
                        return "Not stable"
    return "Stable"


N = int(eval(input()))
R = list(input().split())
C = R[:]
BS_R = bubble_sort(R, N)
SS_R = select_sort(C, N)
print((*BS_R))
print((stable_sort(R, BS_R)))
print((*SS_R))
print((stable_sort(R, SS_R)))

def selectionSort(n, A):
    cnt = 0
    for i in range(n):
        minj = i
        for j in range(i, n):
            if A[minj][1] > A[j][1]:
                minj = j
        if i != minj:
            A[i], A[minj] = A[minj], A[i]
            cnt += 1
    return A


def bubbleSort(n, A):
    flag = True
    cnt = 0
    while flag:
        flag = False
        for j in range(n - 1, 0, -1):
            if A[j - 1][1] > A[j][1]:
                A[j - 1], A[j] = A[j], A[j - 1]
                cnt += 1
                flag = True
    return A


def stableSort(input, output):
    n = len(input)
    for i in range(n):
        for j in range(i + 1, n):
            for a in range(n):
                for b in range(a + 1, n):
                    if (
                        input[i][1] == input[j][1]
                        and input[i] == output[b]
                        and input[j] == output[a]
                    ):
                        return print("Not stable")
    return print("Stable")


if __name__ == "__main__":
    n = int(input())
    R = list(map(str, input().split()))
    C = R[:]
    D = R[:]  # ????????¨?????????
    SR = selectionSort(n, R)
    BR = bubbleSort(n, C)
    print(*BR)
    stableSort(D, BR)
    print(*SR)
    stableSort(D, SR)

-def bubble_sort(r, n): -    flag = True  # ??£??\????´?????????¨????????° +def selectionSort(n, A): +    cnt = 0 +    for i in range(n): +        minj = i +        for j in range(i, n): +            if A[minj][1] > A[j][1]: +                minj = j +        if i != minj: +            A[i], A[minj] = A[minj], A[i] +            cnt += 1 +    return A + + +def bubbleSort(n, A): +    flag = True +    cnt = 0 -        for i in range(n - 1, 0, -1): -            if r[i - 1][1] > r[i][1]: -                r[i - 1], r[i] = r[i], r[i - 1] +        for j in range(n - 1, 0, -1): +            if A[j - 1][1] > A[j][1]: +                A[j - 1], A[j] = A[j], A[j - 1] +                cnt += 1 -    return r +    return A -def select_sort(r, n): -    for i in range(0, n): -        minj = i -        for j in range(i, n): -            if r[j][1] < r[minj][1]: -                minj = j -        if i != minj: -            r[i], r[minj] = r[minj], r[i] -    return r +def stableSort(input, output): +    n = len(input) +    for i in range(n): +        for j in range(i + 1, n): +            for a in range(n): +                for b in range(a + 1, n): +                    if ( +                        input[i][1] == input[j][1] +                        and input[i] == output[b] +                        and input[j] == output[a] +                    ): +                        return print("Not stable") +    return print("Stable") -def stable_sort(r, sort_r): -    for i in range(len(r)): -        for j in range(i + 1, len(r)): -            for a in range(len(sort_r)): -                for b in range(a + 1, len(sort_r)): -                    if r[i][1] == r[j][1] and r[i] == sort_r[b] and r[j] == sort_r[a]: -                        return "Not stable" -    return "Stable" - - -N = int(eval(input())) -R = list(input().split()) -C = R[:] -BS_R = bubble_sort(R, N) -SS_R = select_sort(C, N) -print((*BS_R)) -print((stable_sort(R, BS_R))) -print((*SS_R)) -print((stable_sort(R, SS_R))) +if __name__ == "__main__": +    n = int(input()) +    R = list(map(str, input().split())) +    C = R[:] +    D = R[:]  # ????????¨????????? +    SR = selectionSort(n, R) +    BR = bubbleSort(n, C) +    print(*BR) +    stableSort(D, BR) +    print(*SR) +    stableSort(D, SR)