Felix6326727/beyond-accuracy-code-comprehension huggingface dataset:
N = int(input())
A = list(input().split())
A_ = A.copy()
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]
s = ''
for a in A_:
    s += a + ' '
print(s.rstrip())
print('Stable')


for i in range(N):
    minj = i
    for j in range(i, N):
        if A[j][1] < A[minj][1]:
            minj = j
    A[i], A[minj] = A[minj], A[i]

s_ = ''
for a in A:
    s_ += a + ' '
print(s_.rstrip())
if A == A_:
    print('Stable')
else:
    print('Not stable')



# Example run
# Input:
-3405
`T?9^j3
# Output:
`T?9^j3
Stable
`T?9^j3
Stable
def BubbleSort(a, n):
    flag = 1
    count = 0
    i = 0
    while flag:
        flag = 0
        for j in reversed(range(i+1,n)):
            if a[j][1] < a[j-1][1]:
                c = a[j]
                a[j] = a[j-1]
                a[j-1] = c
                flag = 1
                count += 1
        i += 1

def SelectionSort(a, N):
    count = 0
    minj = 0
    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:
            count += 1      
        c = a[i]
        a[i] = a[minj]
        a[minj] = c

n = int(input())
s = [x for x in input().split()]
s1 = s.copy()

BubbleSort(s,n)
for i in range(len(s)-1):
    print(s[i],end=' ')
print(s[-1])
print('Stable')

SelectionSort(s1,n)

for i in range(len(s1)-1):
    print(s1[i],end=' ')
print(s1[-1])
if s==s1:
    print('Stable')
else:
    print('Not stable')


# Example run
# Input:
-1243251189
C+:
# Output:
C+:
Stable
C+:
Stable
import copy

class Card:
    def __init__(self, suit, number):
        self.suit = suit
        self.number = number

    def equals(self, card):
        if (card.suit == self.suit) and (card.number == self.number):
            return True
        else:
            return False

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

def selection_sort(cards, n):
    for i in range(n):
        min_j = i
        for j in range(i, n):
            if cards[j].number < cards[min_j].number:
                min_j = j
        if min_j != i:
            cards[i], cards[min_j] = cards[min_j], cards[i]
    return cards

def is_stable(cards1, cards2, n):
    result = True
    for i in range(n):
        if not(cards1[i].equals(cards2[i])):
            result = False
            break
    return result

def print_cards(cards, n):
    print(' '.join([c.suit + str(c.number) for c in cards]))

n = int(input())
cards = [Card(card[0], int(card[1])) for card in input().split()]
cards_bubble = bubble_sort(copy.deepcopy(cards), n)
cards_selection = selection_sort(copy.deepcopy(cards), n)

print_cards(cards_bubble, n)
print('Stable')
print_cards(cards_selection, n)
if is_stable(cards_bubble, cards_selection, n):
    print('Stable')
else:
    print('Not stable')



# Example run
# Input:
-110923
13499019
# Output:
13
Stable
13
Stable
n=int(input())
c=input().split();d=c[:]
for i in range(n-1):
 for j in range(n-i-1):
  if c[j][1]>c[j+1][1]:c[j:j+2]=c[j+1],c[j]
 m=i
 for j in range(i,n):
  if d[m][1]>d[j][1]:m=j
 d[i],d[m]=d[m],d[i]
print(*c);print("Stable")
print(*d);print(['Not s','S'][c==d]+'table')


# Example run
# Input:
-4092419
')Q
# Output:
')Q
Stable
')Q
Stable
N = int(input())

card1 = input()
card2 = card1.split()
card3 = card1.split()

for i in range(N-1):
  for j in range(N-1):
    if card2[N-1-j][1] < card2[N-2-j][1]:
      a = card2[N-1-j]
      b = card2[N-2-j]
      card2[N-2-j] = a
      card2[N-1-j] = b

print(" ".join(map(str,card2)))
print("Stable")

for i in range(N):
  minj = i
  for j in range(i,N):
    if card3[j][1] < card3[minj][1]:
      minj = j
  if not card3[i][1] == card3[minj][1]:
    a = card3[i]
    b = card3[minj]
    card3[i] = b
    card3[minj] = a

print(" ".join(map(str,card3)))


if card2 == card3:
  print("Stable")
else:
  print("Not stable")


# Example run
# Input:
-497
g},,YvY
# Output:
g},,YvY
Stable
g},,YvY
Stable
# coding: utf-8
# Your code here!

class Card:
    def __init__(self, suit, value):
        self.suit = suit
        self.value = value
        

def bubbleSort(A, N):
    flag = 1
    while flag:
        flag = 0;
        for i in reversed(range(1, N)):
            if A[i-1].value > A[i].value:
                A[i-1], A[i] = A[i] , A[i-1]
                flag = 1;
    showResult(A)
    return A

def selectionSort(A, N):
    for i in range(0, N):
        minj = i
        mink = i
        for j in range(i, N):
            if A[mink].value > A[j].value:
                mink = j
        if minj != mink:
            A[minj], A[mink] = A[mink], A[minj]
    showResult(A)
    return A



def showResult(B):
    for i in range(N-1):
        print(B[i].suit+str(B[i].value), end = " ")
    print(B[N-1].suit+str(B[N-1].value))

def isStable(rawA, sortedA):
    rawDic = listToDic(rawA)
    sortedDic = listToDic(sortedA)
    flag = 1
    for key in rawDic:
        if len(rawDic[key]) >= 2:
            for i in range(len(rawDic[key])-1):
                if rawDic[key][i] != sortedDic[key][i]:
                    
                    flag = 0
    if flag:
        print("Stable")
    else:
        print("Not stable")

def listToDic(raw):
    rawDic = {}
    for i in range(len(raw)):
        if rawDic.get(raw[i].value) != None:
            rawDic[raw[i].value].append(raw[i].suit)
        else:
            rawDic[raw[i].value] = [raw[i].suit]
    return rawDic

N = int(input())
A = list(input().split()) 
B = []
for i in range(0, N):
    B.append(Card(A[i][:1], A[i][1:]))
C = tuple(B)
"""
C = []
for i in range(0, N):
    C.append(Card(A[i][:1], A[i][1:]))
D = []
for i in range(0, N):
    D.append(Card(A[i][:1], A[i][1:]))
E = []
for i in range(0, N):
    E.append(Card(A[i][:1], A[i][1:]))

F = tuple(B)
print(B)
"""

bubbleA = bubbleSort(B.copy(), N)
isStable(B.copy(), bubbleA)
selectionA = selectionSort(B.copy(), N)
isStable(B.copy(), selectionA)







# Example run
# Input:
1
/YB4tA{A
# Output:
/YB4tA{A
Stable
/YB4tA{A
Stable
def BubbleSort(C, N):
	for i in range(N):
		for j in reversed(range(i+1, N)):
			if C[j][1] < C[j-1][1]:
				C[j], C[j-1] = C[j-1],C[j]
	return C

def SelectionSort(C, N):
    for i in range(N):
        minj = i
        for j in range(i,N):
            if C[j][1] < C[minj][1]:
                minj = j
        C[i],C[minj] = C[minj],C[i]
    return C
        
N = int(input())
C = input().split()
bubble = BubbleSort(C[:], N)
select = SelectionSort(C[:], N)
print(*bubble)
print("Stable")
print(*select)
print(["Not stable", "Stable"][bubble==select])




# Example run
# Input:
-536687537
$,u|iBS0
# Output:
$,u|iBS0
Stable
$,u|iBS0
Stable
def isStable(lis1, lis2):
    ret = True
    for i in range(len(lis1)-1):
        if lis1[i][1] == lis1[i+1][1]:
           ret = (lis1[i+1] in lis2[(lis2.index(lis1[i])+1):]) and ret
    return ret
    
N = int(input())
cards = input().split()

B = list(cards)
for i in range(N):
    for j in range(N-1, i, -1):
        if B[j][1] < B[j-1][1]:
            temp = B[j]
            B[j] = B[j-1]
            B[j-1] = temp

print(' '.join(B))
print('Stable' if isStable(B, cards) else 'Not stable')

S = list(cards)
for i in range(N):
    minj = i
    for j in range(i, N):
        if S[j][1] < S[minj][1]:
            minj = j
    temp = S[i]
    S[i] = S[minj]
    S[minj] = temp

print(' '.join(S))
print('Stable' if isStable(S, cards) else 'Not stable')


    

# Example run
# Input:
-64990941
'S[L8
# Output:
'S[L8
Stable
'S[L8
Stable
def bubble_sort(a, n):
    for i in range(n):
        for j in range(n - 1, i, -1):
            if a[j]['value'] < a[j - 1]['value']:
                tmp = a[j]
                a[j] = a[j - 1]
                a[j - 1] = tmp


def selection_sort(a, n):
    is_stable = True

    for i in range(n):
        minj = i
        samei = n
        for j in range(i+1, n, 1):
            if a[j]['value'] == a[i]['value']:
                samei = j
            if a[j]['value'] < a[minj]['value']:
                minj = j
                if samei < minj:
                    is_stable = False
        tmp = a[i]
        a[i] = a[minj]
        a[minj] = tmp

    return is_stable

def print_list_split_whitespace(a):
    for x in a[:-1]:
        print(x['design'] + str(x['value']), end=' ')
    print(a[-1]['design'] + str(a[-1]['value']))


n = int(input())

a = input().split()
for i in range(n):
    s = a[i]
    a[i] = {'design': s[0], 'value': int(s[1])}
b = a.copy()
c = a.copy()

bubble_sort(a, n)
print_list_split_whitespace(a)

print("Stable")

is_stable = selection_sort(b, n)
print_list_split_whitespace(b)

if is_stable:
    print("Stable")
else:
    print("Not stable")


# Example run
# Input:
1
"6I?\M&
# Output:
"6
Stable
"6
Stable
import copy

class Card:
    def __init__(self, mark_num):
        self.mark_num = mark_num
        self.mark = mark_num[0]
        self.num = int(mark_num[1:])

def bubble_sort(cards, n):
    flag = True
    while flag:
        flag = False
        for i in reversed(range(1, n)):
            if cards[i].num < cards[i-1].num:
                tmp = cards[i]
                cards[i] = cards[i-1]
                cards[i-1] = tmp
                flag = True
    
    # for c in cards:
    #     print(c.mark_num + " ", end="")

    mark_nums = []
    for c in cards:
        mark_nums.append(c.mark_num)

    print(" ".join(mark_nums))
    print("Stable")

    return cards

    # nums_str = map(str, nums)
    # print(" ".join(cards))
    # print(cards)

def selection_sort(cards, n):
    for i in range(n):
        minj = i
        flag = False
        for j in range(i, n-1):
            if cards[minj].num > cards[j+1].num:
                minj = j+1
                flag = True
        
        if flag:
            tmp = cards[i]
            cards[i] = cards[minj]
            cards[minj] = tmp

    mark_nums = []
    for c in cards:
        mark_nums.append(c.mark_num)

    print(" ".join(mark_nums))

    return cards

def is_stable(cards1, cards2, n):
    is_stable = True
    for i in range(n):
        if cards1[i].mark_num != cards2[i].mark_num:
            is_stable = False
            break

    if is_stable:
        print("Stable")
    else:
        print("Not stable")
    
#     nums_str = map(str, nums)
#     print(" ".join(nums_str))
#     print(count)

if __name__=="__main__":
    n = int(input())
    input_cards = list(input().split())
    card_list = []
    for input_card in input_cards:
        card = Card(input_card)
        card_list.append(card)

    cards_1 = bubble_sort(copy.deepcopy(card_list), n)
    cards_2 = selection_sort(copy.deepcopy(card_list), n)

    is_stable(cards_1, cards_2, n)



# Example run
# Input:
-156960
-16
# Output:
-16
Stable
-16
Stable
def bubble_sort(cards):
    list_length = len(cards)

    for i in range(list_length):
        for j in range(list_length-1,i,-1):
            if int(cards[j][1:]) < int(cards[j-1][1:]):
                cards[j],cards[j-1] = cards[j-1],cards[j]
    return cards

def selection_sort(cards):
    list_length = len(cards)

    for i in range(list_length):
        min_element = i
        for j in range(i+1,list_length):
            if int(cards[j][1:]) < int(cards[min_element][1:]):
                min_element = j
        cards[i],cards[min_element] = cards[min_element],cards[i]
    return cards

n = int(input())
cards = input().split()
bubble_cards = [i for i in bubble_sort(cards)]
selection_cards = [i for i in selection_sort(cards)]

print(' '.join(bubble_cards))
print('Stable')
print(' '.join(selection_cards))
if bubble_cards == selection_cards:
    print('Stable')
else:
    print('Not stable')


# Example run
# Input:
5215966
:q|Hq
# Output:
:q|Hq
Stable
:q|Hq
Stable
def bubblesort(A, N):
    for i in range(N):
        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]
    print(*A)
    return A
    
def selectionsort(A, N):
    for i in range(N):
        minj = i
        for j in range(i+1,N):
            if A[minj][1] > A[j][1]:
                minj = j
        A[minj], A[i] = A[i], A[minj]
    print(*A)
    return A
def judge(A,B,N):
    stable = True
    for m in range(N):
        for n in range(m+1, N):
            for x in range(N):
                for y in range(x+1,N):
                    if A[m][1]==A[n][1] and A[m]==B[y] and A[n]==B[x]:
                        stable = False
    if stable:
        return "Stable"
    else:
        return "Not stable"

N = int(input())
A = list(map(str, input().split(" ")))
B = A.copy()
Bubble = bubblesort(B,N)
print(judge(A,Bubble, N))
B = A.copy()
Selection = selectionsort(B,N)
print(judge(A,Selection, N))



# Example run
# Input:
-15
:{qOu)FA
# Output:
:{qOu)FA
Stable
:{qOu)FA
Stable
n = int(input())
cards = list(input().split())
cardb = cards.copy()
cards = cards.copy()

for i in range(n-1):
    for j in range(n-1,i,-1):
        if int(cardb[j].strip('S''H''C''D')) < int(cardb[j-1].strip('S''H''C''D')):
            cardb[j],cardb[j-1] = cardb[j-1],cardb[j]
for i in range(n):
    if i != n-1:
        print(cardb[i], end=' ')
    else:
        print(cardb[i])
print('Stable')

for i in range(n-1):
    # minj=入れ替える数のindex
    minj = i
    for j in range(i+1,n):
        if int(cards[j].strip('S''H''C''D')) < int(cards[minj].strip('S''H''C''D')):
            minj = j
    if i != minj:
        cards[i],cards[minj] = cards[minj],cards[i]
for i in range(n):
    if i != n-1:
        print(cards[i], end=' ')
    else:
        print(cards[i])

judge = True
for i in range(n):
    if cardb[i] != cards[i]:
        judge = False
if judge == True:
    print('Stable')
else:
    print('Not stable')


# Example run
# Input:
-168
/0zig(wme
# Output:
Stable
Stable
# coding: utf-8
# Here your code !
A = int(input())
N = tuple(input().split())
bs=[]
ss=[]
def isStable(a,b):
    leng = int(len(a))
    for i in range(leng):
        for j in range(i+1,leng):
            for x in range(leng):
                for y in range(x+1,leng):
                    if a[i][1]==a[j][1] and a[i]==b[x] and a[j]==b[y]:
                        return "Stable"
    return "Not stable"
    
def bSort(n,a):
    n = list(n)
    for i in range(a):
        for j in range(a-1,i,-1):
            if int(n[j][1]) < int(n[j-1][1]):
                n[j],n[j-1]=n[j-1],n[j]
    return n
    #print(" ".join(n))

    
def seleSort(n,a):
    n = list(n)
    for i in range(a):
        minj = i
        for j in range(i+1,a):
            if n[j][1]<n[minj][1]:
                minj = j
                
        n[i],n[minj]=n[minj],n[i]
    return n
    #print(" ".join(n))

bs = bSort(N,A)
ss = seleSort(N,A)
print(" ".join(bs))
print(isStable(bs,bs))
print(" ".join(ss))
print(isStable(bs,ss))

# Example run
# Input:
-8056
=^6jj+C
# Output:
=^6jj+C
Not stable
=^6jj+C
Not stable
def show(array):
    for i in range(len(array)):
        if (i+1) >= len(array):
            print(array[i])
        else:
            print(array[i], end=' ')


def bubble_sort(c, n):
    for i in range(0, n):
        for j in range(n-1, i, -1):
            if c[j][1:] < c[j-1][1:]:
                c[j], c[j-1] = c[j-1], c[j]

    return c

def selection_sort(c, n):
    for i in range(0, n):
        
        minj = i
        for j in range(i+1, n):
            if c[j][1:] < c[minj][1:]:
                minj = j
        # if i != minj:
        c[i], c[minj] = c[minj], c[i]
    return c


def main():
    N = int(input())
    cards = list(input().split(' '))
    cards2 = cards.copy()

    # value_sorted = sorted(cards, key=lambda x: x[1:])
    bubble_result = bubble_sort(cards, N)
    selection_result = selection_sort(cards2, N)

    show(bubble_result)
    print('Stable')
    show(selection_result)
    if bubble_result == selection_result:
        print('Stable')
    else:
        print('Not stable')


main()


# Example run
# Input:
-929
tx=.[pSe
# Output:
tx=.[pSe
Stable
tx=.[pSe
Stable
import re

N = int(input())

def val(stri):
    a = re.sub(r'\D', '', stri)
    a = int(a)
    return a

def bubble_sort(N, A):
    for i in range(N):
        for j in range(N - 1, i, -1):
            if val(A[j]) < val(A[j - 1]):
                A[j], A[j - 1] = A[j - 1], A[j]
    return A

def selec_sort(N, A):
    for i in range(N):
        minj = i
        for j in range(i + 1, N):
            if val(A[j]) < val(A[minj]):
                minj = j
        A[i], A[minj] = A[minj], A[i]
    return A
    
def isStable(inp, out):
    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 val(inp[i]) == val(inp[j]) and inp[i] == out[b] and inp[j] == out[a]:
                        return False
    return True



def main():
    A = input().split()

    ST = ''
    for i in A:
        ST += i + ' '
    ST.rstrip(' ')

    bubble_sort(N, A)
    B = ST.split()

    print(*A)
    


    if isStable(A, B):
        print('Stable')
    else:
        print('Not stable')
    A = ST.split()
    selec_sort(N, A)
    B = ST.split()

    print(*A)
    

    if isStable(A, B):
        print('Stable')
    else:
        print('Not stable')

main()




# Example run
# Input:
-820
?bK'HaWB
# Output:
?bK'HaWB
Stable
?bK'HaWB
Stable
def select(S):
    for i in range(0, n):
        minj = i
        for j in range(i, n):
            if int(S[j][1]) < int(S[minj][1]):
                minj = j
        (S[i], S[minj]) = (S[minj], S[i])
    return S

def bubble(B):
    flag = True
    while flag:
        flag = False
        for j in reversed(range(1, n)):
            if int(B[j][1]) < int(B[j-1][1]):
                (B[j-1], B[j]) = (B[j], B[j-1])
                flag = True
    return B

n = int(input())
A = input().split(' ')

B = bubble(A[:])
print(" ".join(B[:]))
print("Stable")
S = select(A)
print(" ".join(S))
print("Stable" if " ".join(B) == " ".join(S) else "Not stable")

# Example run
# Input:
-31
6ej=k^S/8
# Output:
6ej=k^S/8
Stable
6ej=k^S/8
Stable
# coding=utf-8

def print_list(X):
    first_flag = True
    for val in X:
        if first_flag:
            print_line = str(val)
            first_flag = False
        else:
            print_line = print_line + ' ' + str(val)
    print(print_line)

def combine_list(A_suit, A_rank, N):
    A_after = []
    for i in range(N):
        A_after.append(A_suit[i] + str(A_rank[i]))
    return A_after


def bubble_sort(A, index_list, N):
    #print_list(A)
    #flag: ???????????????????????????True???????´?
    flag = True
    i = 0
    while flag:
        flag = False
        for j in range(N-1, i, -1):
            if A[j] < A[j-1]:
                A[j-1], A[j] = A[j], A[j-1]
                index_list[j-1], index_list[j] = index_list[j], index_list[j-1]
                flag = True
        i += 1
    return A, index_list

def selection_sort(A, index_list, N):
    for i in range(N):
        min_j = i
        for j in range(i, N):
            if A[j] < A[min_j]:
                min_j = j
        if i != min_j:
            A[i], A[min_j] = A[min_j], A[i]
            index_list[i], index_list[min_j] = index_list[min_j], index_list[i]
    return A, index_list

def main():
    N = int(input())
    A = list(input().split())
    A_suit = []
    A_rank = []
    index_list = [x for x in range(N)]
    A_after_bubble = []
    A_after_selection = []

    for element in A:
        val = list(element)
        val_suit = val[0]
        val_rank = int(val[1])
        A_suit.append(val_suit)
        A_rank.append(val_rank)
    A_suit_after_bubble = [0 for x in range(N)]
    A_suit_after_selection = [0 for x in range(N)]

    A_rank_after_bubble, index_list_after_bubble = bubble_sort(A_rank.copy(), index_list.copy(), N)
    A_rank_after_selection, index_list_after_selection = selection_sort(A_rank.copy(), index_list.copy(), N)

    for index_before, index_after in enumerate(index_list_after_bubble):
        A_suit_after_bubble[index_before] = A_suit[index_after]

    for index_before, index_after in enumerate(index_list_after_selection):
        A_suit_after_selection[index_before] = A_suit[index_after]

    A_after_bubble = combine_list(A_suit_after_bubble, A_rank_after_bubble, N)
    A_after_selection = combine_list(A_suit_after_selection, A_rank_after_selection, N)

    print_list(A_after_bubble)
    print("Stable")
    print_list(A_after_selection)
    if A_after_selection == A_after_bubble:
        print("Stable")
    else:
        print("Not stable")



if __name__ == '__main__':
    main()

# Example run
# Input:
1
-38175
# Output:
-3
Stable
-3
Stable
n = int(input())
c = input().split()

cb = c[:]
for i in range(n):
	for j in range(n-1,i,-1):
		if cb[j][1] < cb[j-1][1]:
			cb[j-1],cb[j] = cb[j],cb[j-1]
print(*cb)
print('Stable')

cs = c[:]
for i in range(n):
	m = min(range(i,n), key=lambda j: cs[j][1])
	if i != m:
		cs[i],cs[m] = cs[m],cs[i]
print(*cs)
print('Stable' if cb == cs else 'Not stable')


# Example run
# Input:
0
UUuK
# Output:
UUuK
Stable
UUuK
Stable
import copy

n=int(input())
s=input().split(' ')
s1=[]
s2=[]
s1=copy.deepcopy(s)
s2=copy.deepcopy(s)

def Bubble_Sort(n,s1):
	m=0
	flag=1
	while flag:
		flag=0
		for i in range(1,n):
			j=n-i
			if int(s1[j][1])<int(s1[j-1][1]):
				a=s1[j]
				s1[j]=s1[j-1]
				s1[j-1]=a
				m+=1
				flag=1
	b=s1
	return(b)

def Selection_Sort(n,s2):
	m=0
	for i in range(n):
		minj=i
		for j in range(i,n):
			if int(s2[j][1])<int(s2[minj][1]):
				minj=j
		if i!=minj:
			a=s2[minj]
			s2[minj]=s2[i]
			s2[i]=a
			m+=1
	b=s2
	return(b)

s1=Bubble_Sort(n,s1)
s2=Selection_Sort(n,s2)

print(s1)
print('stable')
print(s2)
if s1==s2:
	print('Stable')
else:
	print('Not stable')


# Example run
# Input:
-29588
s8H2
# Output:
['s8H2']
stable
['s8H2']
Stable
# -*- coding: utf-8 -*-
"""
Created on Sun Jun 18 10:01:05 2017

@author: syaga
"""

if __name__ == "__main__":
    N = int(input())
    C = list(input().split())
    D = C[:]

    # Bunbble Sort
    for i in range(0, N):
        for j in range(N-1, i, -1):
            if int(C[j][1]) < int(C[j-1][1]):
                temp = C[j]
                C[j] = C[j-1]
                C[j-1] = temp
    print(" ".join(C))
    print("Stable")

    # Selection Sort
    for i in range(0, N):
        minj = i
        for j in range(i, N):
            if int(D[j][1]) < int(D[minj][1]):
                minj = j
        temp = D[i]
        D[i] = D[minj]
        D[minj] = temp
    print(" ".join(D))
    flag = 0
    for (i, j) in zip(C, D):
        if i != j:
            flag = 1
            break
    if flag == 1:
        print("Not stable")
    else:
        print("Stable")

# Example run
# Input:
-902193
`e@@)}rTV
# Output:
`e@@)}rTV
Stable
`e@@)}rTV
Stable
def bubblesort(a,n):
    flag=1
    while flag:
        flag=0
        for j in range(n-1,0,-1):
            if int(a[j][1])<int(a[j-1][1]):
                m=a[j]
                a[j]=a[j-1]
                a[j-1]=m
                flag=1
    return a

def selectionsort(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:
            m=a[i]
            a[i]=a[minj]
            a[minj]=m
    return a

n=int(input())
a=list(input().split( ))
b=[a[i] for i in range(n)]
a1=bubblesort(a,n)
print(" ".join(a1))
print("Stable")
a2=selectionsort(b,n)
print(" ".join(a2))
if a1==a2:
    print("Stable")
else:
    print("Not stable")



# Example run
# Input:
-34
G9$uz\!r(
# Output:
G9$uz\!r(
Stable

Not stable