N = int(eval(input()))

a = [(s[0], int(s[1])) for s in input().split()]



def bubble(a):

    n = len(a)

    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]

    return a



def selection(a):

    n = len(a)

    for i in range(n):

        minj = i

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

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

                minj = j

        a[i], a[minj] = a[minj], a[i]



    return a



b_a = bubble(a[:])

s_a = selection(a[:])



print((" ".join([p[0]+str(p[1]) for p in b_a])))

print("Stable")

print((" ".join([p[0]+str(p[1]) for p in s_a])))

print(("Stable" if b_a==s_a else "Not stable"))
def bubble_sort(a, n):

    for i in range(n-1):

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

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

                a[j-1], a[j] = a[j], a[j-1]



    return a





def selection_sort(a, n):

    for i in range(n-1):

        min_j = i

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

            if a[min_j][1] > a[j][1]:

                min_j = j

        if min_j != i:

            a[min_j], a[i] = a[i], a[min_j]



    return a





if __name__ == "__main__":

    n = int(eval(input()))

    a = input().split()



    result1 = bubble_sort(a[:], n)

    result2 = selection_sort(a[:], n)

    print((*result1))

    print("Stable")

    print((*result2))

    print(("Stable" if result1 == result2 else "Not stable"))

N = int(eval(input()))
a = [(s[0], int(s[1])) for s in input().split()]


def bubble(a):
    n = len(a)
    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]
    return a


def selection(a):
    n = len(a)
    for i in range(n):
        minj = i
        for j in range(i + 1, n):
            if a[j][1] < a[minj][1]:
                minj = j
        a[i], a[minj] = a[minj], a[i]
    return a


b_a = bubble(a[:])
s_a = selection(a[:])
print((" ".join([p[0] + str(p[1]) for p in b_a])))
print("Stable")
print((" ".join([p[0] + str(p[1]) for p in s_a])))
print(("Stable" if b_a == s_a else "Not stable"))

def bubble_sort(a, n):
    for i in range(n - 1):
        for j in range(n - 1, i, -1):
            if a[j - 1][1] > a[j][1]:
                a[j - 1], a[j] = a[j], a[j - 1]
    return a


def selection_sort(a, n):
    for i in range(n - 1):
        min_j = i
        for j in range(i + 1, n):
            if a[min_j][1] > a[j][1]:
                min_j = j
        if min_j != i:
            a[min_j], a[i] = a[i], a[min_j]
    return a


if __name__ == "__main__":
    n = int(eval(input()))
    a = input().split()
    result1 = bubble_sort(a[:], n)
    result2 = selection_sort(a[:], n)
    print((*result1))
    print("Stable")
    print((*result2))
    print(("Stable" if result1 == result2 else "Not stable"))

-N = int(eval(input())) -a = [(s[0], int(s[1])) for s in input().split()] - - -def bubble(a): -    n = len(a) -    for i in range(n): +def bubble_sort(a, n): +    for i in range(n - 1): -            if a[j][1] < a[j - 1][1]: -                a[j], a[j - 1] = a[j - 1], a[j] +            if a[j - 1][1] > a[j][1]: +                a[j - 1], a[j] = a[j], a[j - 1] -def selection(a): -    n = len(a) -    for i in range(n): -        minj = i +def selection_sort(a, n): +    for i in range(n - 1): +        min_j = i -            if a[j][1] < a[minj][1]: -                minj = j -        a[i], a[minj] = a[minj], a[i] +            if a[min_j][1] > a[j][1]: +                min_j = j +        if min_j != i: +            a[min_j], a[i] = a[i], a[min_j] -b_a = bubble(a[:]) -s_a = selection(a[:]) -print((" ".join([p[0] + str(p[1]) for p in b_a]))) -print("Stable") -print((" ".join([p[0] + str(p[1]) for p in s_a]))) -print(("Stable" if b_a == s_a else "Not stable")) +if __name__ == "__main__": +    n = int(eval(input())) +    a = input().split() +    result1 = bubble_sort(a[:], n) +    result2 = selection_sort(a[:], n) +    print((*result1)) +    print("Stable") +    print((*result2)) +    print(("Stable" if result1 == result2 else "Not stable"))