Felix6326727/beyond-accuracy-code-comprehension huggingface dataset:
n = int(input())
cards = input().split()


def print_stable(original_list, sorted_list):
    for n in range(1, 10):
        original_list_n = filter(lambda card: int(card[1]) == n, original_list)
        sorted_list_n = filter(lambda card: int(card[1]) == n, sorted_list)
        is_same = all(map(lambda c: c[0] == c[1], zip(original_list_n, sorted_list_n)))
        if not is_same:
            print('Not stable')
            return
    print('Stable')


def print_list(l):
    print(' '.join(map(str, l)))


def bubble_sort(l):
    swapped = True
    while swapped:
        swapped = False
        for i in range(n - 1, 0, -1):
            if l[i][1] < l[i - 1][1]:
                l[i], l[i - 1] = l[i - 1], l[i]
                swapped = True
    return l


def selection_sort(l):
    for i in range(n - 1):
        min_index = i
        for j in range(i + 1, n):
            if l[j][1] < l[min_index][1]:
                min_index = j
        l[i], l[min_index] = l[min_index], l[i]
    return l


bubble_list = bubble_sort(cards[:])
print_list(bubble_list)
print_stable(cards, bubble_list)

selection_list = selection_sort(cards[:])
print_list(selection_list)
print_stable(cards, selection_list)



# Example run
# Input:
0
8131
# Output:
8131
Stable
8131
Stable
n = int(input())
a = list(map(str,input().split()))

data1 = a[:]
data2 = a[:]

def bubble_sort(data):
	for i in range(len(data)):
		for j in range(len(data)-1,i,-1):
			if(data[j][1] < data[j-1][1]):
				data[j],data[j-1] = data[j-1],data[j]

	return(data)

def selection_sort(data):
	for i in range(len(data)):
		minj = i
		for j in range(i,len(data)):
			if(data[j][1] < data[minj][1]):
				minj = j

		data[i],data[minj] = data[minj],data[i]

	return(data)
data1 = bubble_sort(data1)
data2 = selection_sort(data2)
print(*data1)
print("Stable")
print(*data2)
print("Stable" if data1 == data2 else "NotStable")



# Example run
# Input:
-2
BFR
# Output:
BFR
Stable
BFR
Stable
l, r=len, range
N= int(input())
c1= input().split()
c2=c1[:]
for i in r(l(c1)):
    for j in r(i+1, l(c1))[::-1]:
        if c1[j][1]< c1[j-1][1]:
            c1[j], c1[j-1]= c1[j-1], c1[j]

    m= i
    for j in r(i, l(c2)):
        if c2[j][1] < c2[m][1]: m= j
    c2[i], c2[m]= c2[m], c2[i]
print(*c1)
print("Stable")
print(*c2)
print("Stable" if c1==c2 else "Not stable")

# Example run
# Input:
1
tcM
# Output:
tcM
Stable
tcM
Stable
import copy

def bubble_sort(C, N):
    for i in range(N):
        for j in range(N-1, i, -1):
            if C[j]['value'] < C[j-1]['value']:
                C[j], C[j-1] = C[j-1], C[j]


def selection_sort(C, N):
    for i in range(N):
        min_j = i
        for j in range(i, N):
            if C[j]['value'] < C[min_j]['value']:
                min_j = j
        C[i], C[min_j] = C[min_j], C[i]


if __name__ == "__main__":
    N = int(input())
    C = list(map(lambda c: {'suit': c[0:1],'value': int(c[-1])}, input().split()))
    C2 = copy.deepcopy(C)
    bubble_sort(C, N)
    print(' '.join(map(lambda x: x['suit']+str(x['value']), C)))
    print('Stable')  # bubblesort is definitely Stable sort

    selection_sort(C2, N)
    print(' '.join(map(lambda x: x['suit']+str(x['value']), C2)))
    for bc, sc in zip(C, C2):
        if bc['suit'] != sc['suit']:
            print('Not stable')
            exit()
    print('Stable')



# Example run
# Input:
-41270
-2
# Output:
-2
Stable
-2
Stable
import copy

n = int(input())
A = list (map(str, input().split()))
B = copy.copy(A) 

def BubbleSort_dict(A, n):
    flag = 1    
    while flag:
        flag = 0
        for i in reversed(range(n-1)):
            if int(A[i][1]) > int(A[i+1][1]):
                a = A[i]
                A[i] = A[i+1]
                A[i+1] = a
                flag = 1
    return A
    
def SelectionSort_dict(A, n):
    for i in range(n):
        minj = i
        for j in range(i, n):
            if int(A[j][1]) < int(A[minj][1]):
                minj = j
        if i != minj:
            a = A[i]
            A[i] = A[minj]
            A[minj] = a
    return A

A1 = BubbleSort_dict(A, n)
A2 = SelectionSort_dict(B, n)

print(' '.join(A1))
print("Stable")
print(' '.join(A2))
if A1 == A2:
    print("Stable")
else:
    print("Not stable")


# Example run
# Input:
-101281970
NtQ5EY{
# Output:
NtQ5EY{
Stable
NtQ5EY{
Stable
N = int(input())
A1 = list(map(str,input().split()))
A2 = A1[:]

def bubbleSort(A, N):
 flag = 0
 i = 0
 while flag == 0:
  flag = 1
  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]
    flag = 0
  i += 1
 return A

def selectSort(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 A[i][1] != A[minj][1]:
   A[i], A[minj] = A[minj], A[i]
 return A

def stable(Ab, As, N):
 for i in range(N):
  if Ab[i] != As[i]:
   return False
 return True

bubbleSort(A1, N)
selectSort(A2, N)
print(" ".join(map(str, A1)))
print("Stable")
print(" ".join(map(str, A2)))
if stable(A1, A2, N):
 print("Stable")
else:
 print("Not Stable")

# Example run
# Input:
-1836
@53vp2<ju
# Output:
@53vp2<ju
Stable
@53vp2<ju
Stable
# 配列の宣言
A = []
B = []
C = []

# 文字列の取得と加工
LENGTH =int(input())
A = input().split()
B = A.copy()
C = A.copy()

def bubble (A, LENGTH):
    N = 0
    M = LENGTH - 1
    CHANGE = 0

    while N <= LENGTH -1:
        M = LENGTH - 1
        while M >= N + 1:
            if int(A[M][1:]) < int(A[M-1][1:]):
                tmp = A[M-1]
                A[M-1] = A[M]
                A[M] = tmp
                CHANGE += 1
            M -= 1
        N += 1

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

def selection (B, LENGTH):
    i = 0
    CHANGE_COUNT = 0

    while i <= LENGTH -1:
        j = i + 1
        mini = i
        while j <= LENGTH -1:
            if int(B[j][1:]) < int(B[mini][1:]):
                mini = j
            j += 1
        if mini != i:
            tmp = B[i]
            B[i] = B[mini]
            B[mini] = tmp
            CHANGE_COUNT += 1
        i += 1

    print(" ".join(map(str,B)))
    if B == C:
        print("Stable")
    else:
        print("Not Stable")

bubble (A, LENGTH)
selection (B, LENGTH)


# Example run
# Input:
-15303
@?c7P~Hd
# Output:
@?c7P~Hd
Stable
@?c7P~Hd
Stable
def bubble_sort(cards, n):
#2   for i = 0 to N-1
#3     for j = N-1 downto i+1
#4       if C[j].value < C[j-1].value
#5         C[j] と C[j-1] を交換
    for i in range(0, n):
        for j in range(n-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, n):

#8   for i = 0 to N-1
#9     minj = i
#10    for j = i to N-1
#11      if C[j].value < C[minj].value
#12        minj = j
#13    C[i] と C[minj] を交換
    for i in range(0, n-1):
        minj = i
        for j in range(i, n):
            if int(cards[j][1]) <  int(cards[minj][1]):
                minj = j
        cards[i], cards[minj] = cards[minj], cards[i]
    
    return cards


n = int(input())
cards = input().split()
list_buble = bubble_sort(cards[:], n)
list_selection = selection_sort(cards[:], n)
print(*list_buble)
print("Stable")
print(*list_selection)
print("Stable" if list_buble == list_selection else "Not stable")



# Example run
# Input:
-224960337
syT!3N
# Output:
syT!3N
Stable
syT!3N
Stable
def bubble(c):
	for i in range(len(c)):
		for j in range(len(c)-1,i,-1):
			if int(c[j][-1]) < int(c[j-1][-1]):
				c[j],c[j-1] = c[j-1],c[j]
	return c

def selection(c):
	for i in range(len(c)):
		mini = i
		for j in range(i,len(c)):
			if int(c[j][-1])<int(c[mini][-1]):
				mini = j
	c[i],c[mini]=c[mini],c[i]
	return c

n = int(input())
card = list(map(str,input().split()))
card1 = card
bubble(card)
selection(card1)
print(" ".join(map(str,card)))
print("Stable")
print(" ".join(map(str,card1)))
print("Stable") if card==card1 else ("Not stable")

# Example run
# Input:
-33
-3724
# Output:
-3724
Stable
-3724
Stable
N = int(input())
C = list(input().split())
_C = C.copy()

for i in range(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]
print(*C)
print("Stable")

for j in range(N):
    m = i
    for j in range(i, N):
        if (_C[j][1] < _C[j-1][1]):
            m = j
    _C[i], _C[m] = _C[m], _C[i]
print(*_C)
if(C ==_C):
    print("Stable")
else:
    print("Not stable")

# Example run
# Input:
-233787
YVxv>z%!
# Output:
YVxv>z%!
Stable
YVxv>z%!
Stable
def bubbleSort(cards, N):
    flag = True
    while flag:
        flag = False
        for j in range(N-1, 0, -1):
            if cards.numbers[j] < cards.numbers[j - 1]:
                cards.swap(j, j-1)
                flag = True
    return cards

def selectionSort(cards,N):
    for i in range(N):
        minj = i
        for j in range(i, N):
            if cards.numbers[j] < cards.numbers[minj]:
                minj = j
        if minj != i:
            cards.swap(i, minj)
    return cards

class Cards(object):
    
    def __init__(self, cards):
        self.cards = cards
        self.numbers = [int(card[1]) for card in cards]

    def filter_by_number(self, number):
        return [card for card in self.cards if card.endswith(str(number))]

    def swap(self, i, j):
        self.cards[i], self.cards[j] = self.cards[j], self.cards[i]
        self.numbers = [int(card[1]) for card in self.cards]

    def show(self):
        print(' '.join(self.cards))

    def is_stable(self, cards):
        for n in range(1,10):
            suits_x = self.filter_by_number(str(n))
            suits_y = cards.filter_by_number(str(n))
            if suits_x != suits_y:
                return False
        return True

    def copy(self):
        return Cards([card for card in self.cards])

def run():
    n = int(input())
    cards = Cards(input().split())
    cards_sorted = bubbleSort(cards.copy(),n)
    cards_sorted.show()
    if cards.is_stable(cards_sorted):
        print('Stable')
    else:
        print('Not stable')

    cards_sorted = selectionSort(cards.copy(),n)
    cards_sorted.show()
    if cards.is_stable(cards_sorted):
        print('Stable')
    else:
        print('Not stable')

if __name__ == '__main__':
    run()


# Example run
# Input:
0
-84521052
# Output:
-84521052
Stable
-84521052
Stable
def BubbleSort(C, N):

    for i in range(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 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

def isStable(C1, C2, N):
    if C1 != C2:
        return "Stable"
    return "Not stable"

Num = int(input())
Cards = [x for x in input().split()]
card1 = BubbleSort(list(Cards), Num)
card2 = SelectionSort(list(Cards), Num)

print(" ".join(card1))
print(isStable(card1, card1, Num))
print(" ".join(card2))
print(isStable(card1, card2, Num))



# Example run
# Input:
1
WAS`~
# Output:
WAS`~
Not stable
WAS`~
Not stable
import copy

def bubbleSort(A):
    flag = 1
    while flag:
        flag = 0
        for j in range(len(A)-1,0,-1):#こういう書き方なんや……逆順処理
            if int(A[j][1]) < int(A[j-1][1]):
                A[j],A[j-1] = A[j-1],A[j]
                flag += 1
    return A

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

N = int(input())
lst1 = list(input().split())
lst2 =  copy.copy(lst1)
print(" ".join(bubbleSort(lst1)))
print("Stable")
print(" ".join(selectionSort(lst2)))
if lst1 == lst2:
    print("Stable")
else:
    print("Not stable")


# Example run
# Input:
-4934
203
# Output:
203
Stable
203
Stable
#import copy

n=int(input())
A=input().split()
C=A[:] #参照渡しのため

def bubble_sort(n,A):
  flag=True
  i=0
  while flag:
    flag=False
    for j in reversed(range(i+1,n)):
      if int(A[j][1])<int(A[j-1][1]):
        tmp=A[j]
        A[j]=A[j-1]
        A[j-1]=tmp
        flag=True
    i+=1
  return A

def selection_sort(n,A):
  for i in range(n):
    minj=i
    for j in range(i+1,n):
      #print(A[minj],A[j])
      if int(A[j][1])<int(A[minj][1]):
        minj=j
    tmp=A[i]
    A[i]=A[minj]
    A[minj]=tmp
    # 途中で入れ替わるからnot stable
    #print("---")
  return A

x=bubble_sort(n,A)
y=selection_sort(n,C)
print(*x) # stable
print('Stable')
print(*y) # not stable
print('Stable' if x==y else 'Not stable')



# Example run
# Input:
-166
4EPy
# Output:
4EPy
Stable
4EPy
Stable
class Card:
    def __init__(self, suit='', num=''):
        self.suit = suit
        self.num = num
    def __str__(self):
        return "" + self.suit + self.num

def bubble_sort(list):
    for i in range(n):
        for j in range(n - 1, i, -1):
            if list[j].num < list[j - 1].num:
                tmp = list[j]
                list[j] = list[j - 1]
                list[j - 1] = tmp

def selection_sort(list):
    for i in range(n):
        mini = i
        for j in range(i+1, n):
            if list[j].num < list[mini].num:
                mini = j
        tmp = list[mini]
        list[mini] = list[i]
        list[i] = tmp

n = int(input())
inputs = [string for string in input().split(" ")]

cards = []
for i in range(n):
    cards.append(Card(inputs[i][0], inputs[i][1]))

selection_cards = cards.copy()

bubble_sort(cards)
selection_sort(selection_cards)

bubble_result = str(cards[0])
for i in range(1, n):
    bubble_result += " " + str(cards[i]);
print(bubble_result)
print("Stable")

selection_result = str(selection_cards[0])
stable_flag = (cards[0] == selection_cards[0])
for i in range(1, n):
    if cards[i] != selection_cards[i]:
        stable_flag = False
    selection_result += " " + str(selection_cards[i])
print(selection_result)
if stable_flag:
    print("Stable")
else:
    print("Not stable")


# Example run
# Input:
1
;RvkF,
# Output:
;R
Stable
;R
Stable
def bubbleSort(A, N):
    flag = True
    while flag:
        flag = False
        for j in range(N-1,0,-1):
            if A[j][-1:] < A[j-1][-1:]:
                A[j],A[j-1] = A[j-1],A[j]
                flag = True
    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 A[i][-1:] != A[minj][-1:]:
            A[i],A[minj] = A[minj],A[i]
    return A
    
def isStable(st,list2):
    for i in range(1,len(st)):
        if list2[i][-1:] == list2[i-1][-1:]:
            if st[i] != list2[i]:
                return "Not stable"
    return "Stable"
    
num = int(input())
li1 = input().split()
stli = bubbleSort(li1[:],num)
li2 = bubbleSort(li1[:],num)
print(*li2,sep=" ")
print(isStable(stli,li2))
li3 = selectionSort(li1[:],num)
print(*li3,sep=" ")
print(isStable(stli[:],li3))


# Example run
# Input:
-19
`C^
# Output:
`C^
Stable
`C^
Stable
n = int(input())
A = input().rstrip().split()
B = list(map(lambda x:int(x[1]), A))
C = list(enumerate(B))
D = list(enumerate(B))

Cb = C
nums = [n - i for i in range(1, n)]
flag = 1

while flag == 1:
    flag = 0
    for j in nums:
        if Cb[j][1] < Cb[j - 1][1]:
            Cb[j], Cb[j - 1] = Cb[j - 1], Cb[j]
            flag = 1
        else:
            pass
Ab = [A[Cb[i][0]] for i in range(n)]
print(*Ab)
bstable = 1
for j in range(n - 1):
    if Cb[j + 1][1] == Cb[j][1] and Cb[j + 1][0] < Cb[j][0]:
        bstable = 0
        break
if bstable == 1:
    print("Stable")
else:
    print("Not stable")

Cs = D
for i in range(n):
    minj = i
    for j in range(i, n):
        if Cs[j][1] < Cs[minj][1]:
            minj = j
        else:
            pass
    Cs[i], Cs[minj] = Cs[minj], Cs[i]
    
As = [A[Cs[i][0]] for i in range(n)]
print(*As)
cstable = 1
for j in range(n - 1):
    if Cs[j + 1][1] == Cs[j][1] and Cs[j + 1][0] < Cs[j][0]:
        cstable = 0
        break
if cstable == 1:
    print("Stable")
else:
    print("Not stable")



# Example run
# Input:
-58
-282811832
# Output:

Stable

Stable
n = int(input())
a = [i for i in input().split()]
a2 = a.copy()
for i in range(n):
    for j in reversed(range(i, n)):
        if a[j][1] < a[j-1][1]:
            a[j], a[j-1] = a[j-1], a[j]
for s in range(n):
    minj = s 
    for t in range(s+1, n):
        if a2[t][1] < a2[minj][1]:
            minj = t
    if a2[s] != a2[minj]:
        a2[s], a2[minj] = a2[minj], a2[s]
print(*a)
print("Stable")
print(*a2)
if a == a2:
    print("Stable")
else:
    print("Not stable")


# Example run
# Input:
-197
s3Ec|
# Output:
s3Ec|
Stable
s3Ec|
Stable
# -*- coding: utf-8 -*-
"""
Created on Sat Apr 28 09:21:55 2018
ALDS-1-2c
@author: maezawa
"""

def selection(a, n):
    """
    Selection Sort of array a, n=len(a)
    
    配列aｆは参照渡しなのでa自身が変化する（ソートされる）
    """
    cnt = 0
    for i in range(n):
        flag = 0
        minj = i
        for j in range(i+1,n):
            if int(a[j][1]) < int(a[minj][1]):
                minj = j
                flag = 1
        if flag == 1:
            temp = a[minj]
            a[minj] = a[i]
            a[i] = temp
            cnt += 1
    return cnt

def bubble(a, n):
    cnt = 0
    for i in range(n):
        for j in reversed(range(i+1,n)):
            if int(a[j][1]) < int(a[j-1][1]):
                temp = a[j]
                a[j] = a[j-1]
                a[j-1] = temp
                cnt += 1
    return cnt

def print_array(a):
    ans = str(a[0])
    for i in range(1,n):
        ans += ' '+str(a[i])  
    print(ans)

def is_stable(a, b):
    for card1 in range(len(a)):
        for card2 in range(card1+1,len(a)):
            if a[card1][1] == a[card2][1]:
                if b.index(a[card1]) > b.index(a[card2]):
                    return 'Not stable'
    return 'Stable'

n = int(input())
a = input().split()

bub = a[:]
cnt = bubble(bub, n)   
print_array(bub)
print(is_stable(a, bub))

sel = a[:]
cnt = selection(sel, n)   
print_array(sel)
print(is_stable(a, sel))


# Example run
# Input:
-1309
jtN_
# Output:
jtN_
Stable
jtN_
Stable
import copy

n = int(input())
a = input().split()
b = copy.deepcopy(a)

for i in range(n):
    for j in range(n - 1 - i):
        if int(a[j][1]) > int(a[j + 1][1]):
            tmp = a[j]
            a[j] = a[j + 1]
            a[j + 1] = tmp

ra = " ".join(a)

print(ra)
print("Stable")

for i in range(n - 1):
    minj = i
    for j in range(i + 1, n):
        if int(b[j][1]) < int(b[minj][1]):
            minj = j
    if minj != i:
        tmp = b[i]
        b[i] = b[minj]
        b[minj] = tmp

rb = " ".join(b)
print(rb)

if ra == rb:
    print("Stable")
else:
    print("Not stable")

# Example run
# Input:
-142
*'x-S-PK
# Output:
*'x-S-PK
Stable
*'x-S-PK
Stable
class Card():
    def __init__(self, card):
        self.card = card
        self.mark = card[0]
        self.number = card[1]
        
    def __lt__(self, other):
        if not isinstance(other, Card):
            return NotImplemented
        return self.number < other.number
    
    def __eq__(self, other):
        if not isinstance(other, Card):
            return NotImplemented
        return self.mark == other.mark and self.number == other.number
        
    def __repr__(self):
        return '{}{}'.format(self.mark, self.number)

    def ls_sort(self):
        return


def BubbleSort(target):
    ls = target.copy()
    flag = 1
    while flag:
        flag = 0
        for i in range(len(ls)-1, 0, -1):
            if ls[i] < ls[i-1]:
                ls[i], ls[i-1] = ls[i-1], ls[i]
                flag = 1
    print(' '.join(map(str, ls)))
    return sorted(ls)


def SelectSort(target):
    ls = target.copy()
    for i in range(len(ls)):
        minj = i
        for j in range(i+1, len(ls)):
            if ls[j] < ls[minj]:
                minj = j
        if ls[i] != ls[minj]:
            ls[i], ls[minj] = ls[minj], ls[i]
    
    print(' '.join(map(str, ls)))
    return sorted(ls)

def judge(original, sorted_list):
    if original == sorted_list:
        print('Stable')
    else:
        print('Not stable')


_ = int(input())
l2 =  [Card(i) for i in input().split()]
l2_sort = sorted(l2)

bubble = BubbleSort(l2)
judge(l2_sort, bubble)

select = SelectSort(l2)
judge(l2_sort, select)


# Example run
# Input:
-60
sC{iX7*QR
# Output:
sC
Stable
sC
Stable
length = int(input())
eles = [l for l in input().split()]
is_stable = 'Stable'

import copy
_copy = copy.deepcopy(eles)

for i in range(length):
    for j in range(length-1, 0, -1):
        if _copy[j][1] < _copy[j-1][1]:
            _copy[j], _copy[j-1] = _copy[j-1], _copy[j]

print(*_copy)
print(is_stable)

__copy = copy.deepcopy(eles)

for i in range(length-1):
    _min = i
    for l in range(i, length):
        if __copy[l][1] < __copy[_min][1]:
            _min = l
            is_stable = 'Not Stable'
    __copy[i], __copy[_min] = __copy[_min], __copy[i]

print(*__copy)
print(is_stable)

# Example run
# Input:
-224484380
kF,}Eok"$
# Output:
kF,}Eok"$
Stable
kF,}Eok"$
Stable
N = int(input())
array = list(input().split())
array2 = array[:]
array3 = array[:]

def bubble_sort(array, N):
	flag = 1
	i = 0
	while flag:
		flag = 0 
		j = N-1
		while j > i:
			if array[j][1] < array[j-1][1]:
				array[j], array[j-1] = array[j-1], array[j]
			j -= 1
			flag = 1
		i += 1


def selection_sort(array, n):
	for i in range(n):
		minij = i 
		for j in range(i, n):
			if array[j][1] < array[minij][1]:
			    minij = j 
		array[i], array[minij] = array[minij], array[i]

def is_stable(Input, output, n):
	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][1] == output[b][1] and Input[j][1] == output[a][1]:
						return False
	return True 

bubble_sort(array, N)
print(' '.join(array))
print('Stable')
selection_sort(array2,N)
print(' '.join(array2))
if is_stable(array3, array2, N):
	print('Stable')
else:
	print('Not Stable')







# Example run
# Input:
-1068
|EuxOg\?
# Output:
|EuxOg\?
Stable
|EuxOg\?
Stable
def bubble(A, N):
    flag = True
    while flag:
        flag = False
        for j in range(N-1, 0, -1):
            if int(A[j][-1]) < int(A[j-1][-1]):
                A[j], A[j-1] = A[j-1], A[j]
                flag = True
    return A

def selection(A, N):
    for i in range(0, N):
        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

if __name__ == "__main__":
    N = int(input())
    A = input().split()

    A_bubble = bubble(A[:], N)
    print (*A_bubble)
    print ("Stable")

    A_selection = selection(A[:], N)
    print (*A_selection)
    if A_bubble == A_selection:
        print ("Stable")
    else:
        print ("Not Stable")

# Example run
# Input:
-1355
=D}`tS
# Output:
=D}`tS
Stable
=D}`tS
Stable
def compare_cards(a, b):
    return int(a[1]) < int(b[1])

N = int(input())
C = input().split()

bubbleC = list(C)

#compare_cards(C[0],C[1])
print(*C)

# Example run
# Input:
-1628416575
+CP)0CA
# Output:
+CP)0CA