Felix6326727/beyond-accuracy-code-comprehension huggingface dataset:
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(1000000)


def li_input():
    return [int(_) for _ in input().split()]

def BubbleSort(N, A):

    for i in range(N):
        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]
    
    return A

def SelectionSort(N, A):

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

def is_stable(A, A_):
    for i in range(len(A_) - 1):
        if A_[i][1] == A_[i + 1][1]:
            j = A.index(A_[i])
            k = A.index(A_[i + 1])
            
            if j > k:
                return "Not stable"
    
    return "Stable"

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

    BA = BubbleSort(N, A[:])
    SA = SelectionSort(N, A[:])

    print(" ".join(list(map(str, BA))))
    print(is_stable(A, BA))
    print(" ".join(list(map(str, SA))))
    print(is_stable(A, SA))


main()



# Example run
# Input:
-405
?CWE91W<
# Output:
?CWE91W<
Stable
?CWE91W<
Stable
def BubbleSortChar(c,n):
    num = [int(s[1]) for s in c]
    for i in range(n):
        # n-1からiまでさかのぼっていく
        for j in range(n-1,i,-1):
            # 順番を入れ替える条件
            if num[j-1] > num[j]:
                # 数字のみの入れ替え
                tmp = num[j-1]
                num[j-1] = num[j]
                num[j] = tmp
                # 本物の入れ替え
                tmp = c[j-1]
                c[j-1] = c[j]
                c[j] = tmp
    return " ".join(c)

def SelectionSortChar(c,n):
    num = [int(s[1]) for s in c]
    for i in range(n):
        # print(c)
        minj = i
        for j in range(i,n):
            if num[j] < num[minj]:
                minj = j
        # origin
        tmp = c[minj]
        c[minj] = c[i]
        c[i] = tmp
        #num
        tmp = num[minj]
        num[minj] = num[i]
        num[i] = tmp

    return " ".join(c)




# バブルソートは常に安定ソート
# バブルソートと違う -> Not Stable
N = int(input())
S1 = input().split(" ")
S2 = [s for s in S1]
# Bubble Sort
C1 = BubbleSortChar(S1,N)
print(C1)
print("Stable")

# Selection Sort
C2 = SelectionSortChar(S2,N)
print(C2)
if C1==C2:
    print("Stable")
else:
    print("Not stable")



# Example run
# Input:
-1
2657144
# Output:
2657144
Stable
2657144
Stable
import copy

def Bubble(A,N):
	flag = 1
	while flag:
		flag = 0
		for i in range(N-1,0,-1):
			if int(A[i][1]) < int(A[i-1][1]):
				tmp = A[i]
				A[i] = A[i-1]
				A[i-1] = tmp
				flag = 1

def Selection(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
		tmp = A[i]
		A[i] = A[minj]
		A[minj] = tmp

def isStable(A,B,N):
	for i in range(N):
		if A[i] != B[i]:
			return False
	return True

N = int(input())
A = list(input().split())
B = copy.deepcopy(A)
Bubble(A,N)
Selection(B,N)
print(' '.join([str(a) for a in A]))
print('Stable')
print(' '.join([str(a) for a in B]))
print('Stable') if isStable(A,B,N) else print('Not stable')



# Example run
# Input:
-466739589
<|B^
# Output:
<|B^
Stable
<|B^
Stable
import copy
N = int(input())
A = list(input().split())
C = []
C = copy.deepcopy(A)

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

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


print(*C)
print("Stable")
print(*A)
if A == C:
    print("Stable")
else:
    print("Not stable")


# Example run
# Input:
-56
K]}uU;
# Output:
K]}uU;
Stable
K]}uU;
Stable
def bubblesort(n, a):
    r = a[:]
    for i in range(n):
        for j in range(n-1, i, -1):
            if int(r[j][1]) < int(r[j-1][1]):
                r[j], r[j-1] = r[j-1], r[j]

    print(*r)
    print("Stable")


def selectionsort(n, a):
    r = a[:]
    ret = "Stable"
    for i in range(n):
        tmp = i
        for j in range(i, n):
            if int(r[j][1]) < int(r[tmp][1]):
                tmp = j
        r[i], r[tmp] = r[tmp], r[i]
        if r[i][0] != r[tmp][0] and int(r[i][1]) == int(r[tmp][1]):
            ret = "Not Stable"

    print(*r)
    print(ret)


def main():
    n = int(input())
    a = list(input().split())

    bubblesort(n, a)
    selectionsort(n, a)


if __name__ == '__main__':
    main()



# Example run
# Input:
-10
u}Q
# Output:
u}Q
Stable
u}Q
Stable
# coding: utf-8
# Your code here!
from copy import deepcopy
def selectionSort(A,N):
    lst=deepcopy(A)
    for i in range(N):
        minj=i
        for j in range(i,N):
            if int(lst[j][1])<int(lst[minj][1]):
                minj=j
        lst[i],lst[minj]=lst[minj],lst[i]
    return(lst)

def bubbleSort(A,N):
    lst=deepcopy(A)
    for i in range(N):
        for j in range(N-1,i,-1):
            if int(lst[j][1])<int(lst[j-1][1]):
                lst[j],lst[j-1]=lst[j-1],lst[j]
    return(lst)

a=int(input())
b=input().split(" ")
Selected=selectionSort(b,a)
Bubbled=bubbleSort(b,a)
IsStable="Stable"
for i in range(a):
    if Selected[i] != Bubbled[i]:
        IsStable="Not stable"

print(" ".join(Bubbled),"Stable"," ".join(Selected),IsStable,sep="\n")


# Example run
# Input:
-1131247330
d=C>#:p
# Output:
d=C>#:p
Stable
d=C>#:p
Stable
# https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/2/ALDS1_2_C


def BubbleSort(C, N):
    for i in range(N):
        for j in range(N-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 SelectionSort(C, N):
    for i in range(N):
        minj = i
        for j in range(i, N):
            if int(C[j][1]) < int(C[minj][1]):
                minj = j
        C[i], C[minj] = C[minj], C[i]
    return C


def solve():
    n = int(input())
    l = input().split()
    m = l.copy()

    l = BubbleSort(l, n)
    m = SelectionSort(m, n)

    print(' '.join(l))
    print('Stable')
    print(' '.join(m))
    if l == m:
        print('Stable')
    else:
        print('Not stable')


if __name__ == '__main__':
    solve()



# Example run
# Input:
-7930
8H2.
# Output:
8H2.
Stable
8H2.
Stable
def bubble_sort(seq):
    for i in range(len(seq)):
        flag = 0
        for j in range(len(seq)-1,i,-1):
            if seq[j-1][1] > seq[j][1]:
                seq[j-1],seq[j] = seq[j],seq[j-1]
                flag = 1
        if flag == 0: break
    return seq


def selection_sort(seq):
    for i in range(len(seq)):
        mini = i
        for j in range(i+1,len(seq)):
            if seq[mini][1] > seq[j][1]:mini = j
        seq[i],seq[mini] = seq[mini],seq[i]
    return seq



n = int(input())
*seq,= input().split()
seq2 = seq[:]

bl = bubble_sort(seq)
print(bl)
print("Stable")
sl = selection_sort(seq2)
print(sl)
if bl == sl:print("Stable")
else:print("Not stable")



# Example run
# Input:
-7038374
.z0k`S
# Output:
['.z0k`S']
Stable
['.z0k`S']
Stable
n = int(input())

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

def babble_sort(l):
    for i in range(0, len(l)):
        for j in reversed(range(i+1, len(l))):
            b = int(l[j][1])
            a = int(l[j - 1][1])
            if b < a:
                t = l[j]
                l[j] = l[j-1]
                l[j-1] = t
    return l

def is_stable(a, l):
    for e in a:
        for j in l:
            if e[1] == j[1]:
                if e[0] != j[0]:
                    return False
                else:
                    return True

def print_with_space(l):
    print(' '.join(str(x) for x in l))

babbled = babble_sort(A[:])
print_with_space(babbled)

if is_stable(A, babbled):
    print('Stable')
else:
    print('Not stable')


def selection_sort(l):
    for i in range(0, len(l)):
        minj = i
        for j in range(i, len(l)):
            if int(l[j][1]) < int(l[minj][1]):
                minj = j
        t = l[i]
        l[i] = l[minj]
        l[minj] = t
    return l

selected = selection_sort(A[:])
print_with_space(selected)

if is_stable(A, selected):
    print('Stable')
else:
    print('Not stable')

# Example run
# Input:
-213058
-83
# Output:
-83
Stable
-83
Stable
from copy import copy

def bubbleSort(arr):
    cp_arr = copy(arr)
    indices = list(range(len(cp_arr)))
    
    finished_flag = False
    while not finished_flag:
        finished_flag = True

        for i in range(len(cp_arr)-1):
            if cp_arr[i] > cp_arr[i+1]:
                finished_flag = False

                t = cp_arr[i]
                cp_arr[i] = cp_arr[i+1]
                cp_arr[i+1] = t

                t = indices[i]
                indices[i] = indices[i+1]
                indices[i+1] = t
    return indices

def selectionSort(arr):
    cp_arr = copy(arr)
    indices = list(range(len(cp_arr)))

    for i in range(len(cp_arr)):
        min = i
        for j in range(i+1, len(cp_arr)):
            if cp_arr[j] < cp_arr[min]:
                min = j

        t = cp_arr[i]
        cp_arr[i] = cp_arr[min]
        cp_arr[min] = t

        t = indices[i]
        indices[i] = indices[min]
        indices[min] = t

    return indices

if __name__ == "__main__":
    input()
    cards = input().split()
    values = list(map(lambda x: int(x[1]), cards))
    bubbleSorted_indices = bubbleSort(values)
    selectionSorted_indices = selectionSort(values)
    bubble_stable = True
    selection_stable = True
    for i in range(len(values)-1):
        if values[bubbleSorted_indices[i]] == values[bubbleSorted_indices[i+1]] and bubbleSorted_indices[i] > bubbleSorted_indices[i+1]:
            bubble_stable = False
        if values[selectionSorted_indices[i]] == values[selectionSorted_indices[i+1]] and selectionSorted_indices[i] > selectionSorted_indices[i+1]:
            selection_stable = False
    bubble_sorted = [cards[i] for i in bubbleSorted_indices]
    selection_sorted = [cards[i] for i in selectionSorted_indices]
    print(" ".join(bubble_sorted))
    print("Stable" if bubble_stable else "Not stable") 
    print(" ".join(selection_sorted))
    print("Stable" if selection_stable else "Not stable") 





# Example run
# Input:
F!2eKDu
-84564737
# Output:
-84564737
Stable
-84564737
Stable
N = int(input())
card = list(input().split())

card_buble = card.copy()
card_select = card.copy()

#bubble sort
flag = 1
i = 0
count = 0
while flag==1:
    flag = 0
    for j in range(i+1,len(card_buble))[::-1]:
        if int(card_buble[j][-1]) < int(card_buble[j-1][-1]):
            temp  = card_buble[j]
            card_buble[j] = card_buble[j-1]
            card_buble[j-1] = temp
            flag = 1
    i += 1


#select sort
for i in range(0,len(card_select)):
    mini = i
    for j in range(i,len(card_select)):
        if int(card_select[j][-1]) < int(card_select[mini][-1]):
            mini = j
    temp = card_select[i]
    card_select[i] = card_select[mini]
    card_select[mini] = temp

print(" ".join(card_buble))
print("Stable")

print(" ".join(card_select))
if card_select == card_buble: print("Stable")
else: print("Not stable")





# Example run
# Input:
134
-5930
# Output:
-5930
Stable
-5930
Stable
def bubble_sort(seq):
    for i in range(len(seq)):
        flag = 0
        for j in range(len(seq)-1,i,-1):
            if seq[j-1][1] > seq[j][1]:
                seq[j-1],seq[j] = seq[j],seq[j-1]
                flag = 1
        if flag == 0: break
    return seq


def selection_sort(seq):
    for i in range(len(seq)):
        mini = i
        for j in range(i,len(seq)):
            if seq[mini][1] > seq[j][1]:mini = j
        seq[i],seq[mini] = seq[mini],seq[i]
    return seq



n = int(input())
*seq,= input().split()
seq2 = seq[:]

bl = bubble_sort(seq)
print(bl)
print("Stable")
sl = selection_sort(seq2)
print(sl)
if bl == sl:print("Stable")
else:print("Not stable")



# Example run
# Input:
24485
)Y'\rv^/
# Output:
[")Y'\\rv^/"]
Stable
[")Y'\\rv^/"]
Stable
# -*- coding: UTF-8 -*-
#Stable Sort
import copy

def bubble_sort(bubble_N,bubble_A):
    #バブルソート
    flag = 1
    bi = 0
    # Sort処理（自分メモ：flagが0になったらループを抜ける）
    while flag:
        flag = 0
        for bj in reversed(range(bi + 1, bubble_N)):
            if bubble_A[bj][1:2] < bubble_A[bj - 1][1:2]:
                tmp = bubble_A[bj - 1]
                bubble_A[bj - 1] = bubble_A[bj]
                bubble_A[bj] = tmp
            flag = 1
        bi += 1

def selection_sort(selection_N,selection_A):
    #選択ソート
    for si in range(selection_N):
        cnt_flg = 0
        minj = si
        for sj in range(si, selection_N):
            if selection_A[sj][1:2] < selection_A[minj][1:2]:
                minj = sj
                cnt_flg = 1
        tmp = selection_A[si]
        selection_A[si] = selection_A[minj]
        selection_A[minj] = tmp

#標準入力から
N = int(input()) #要素数
B_A = list(input().split()) #バブルソート対象（スペース区切り→配列に展開）
S_A = copy.deepcopy(B_A) #選択ソート対象（コピー）

bubble_sort(N,B_A) #バブルソート実施
selection_sort(N,S_A) #選択ソート実施
ans_bubble = ' '.join(map(str,B_A)) #配列を文字列に戻す
ans_selection = ' '.join(map(str,S_A)) #配列を文字列に戻す

#バブルソート結果の出力（常にStable）
print(ans_bubble)
print("Stable")

#選択ソート結果の出力（バブルソート結果と比較してStable判断）
print(ans_selection)
if ans_bubble == ans_selection:
    print("Stable")
else:
    print("Not stable")



# Example run
# Input:
-436802
\a&K8&(#
# Output:
\a&K8&(#
Stable
\a&K8&(#
Stable
n = int(input())
lst = input().split()
bub, sel, sts = lst[:], lst[:], []
def stable(sls):
    s = 0
    for l in range(1,n):
        if (sls[l][1] == sls[l-1][1]) * (sts.index(sls[l][0]) < sts.index(sls[l-1][0])):
            s += 1
    print('Not stable' if s else 'Stable')

for i in range(n):
    m = i
    li = lst[i][0]
    if not li in sts:
        sts.append(li)
    for j in range(n-1,i,-1):
        if bub[j][1] < bub[j-1][1]:
            bub[j-1:j+1] = bub[j], bub[j-1]
    for k in range(i, n):
        if sel[k][1] < sel[m][1]:
            m = k
    if m != i:
        sel[i], sel[m] = sel[m], sel[i]

print(*bub)
stable(bub)
print(*sel)
stable(sel)

# Example run
# Input:
-105071
cA'IQxN
# Output:
cA'IQxN
Stable
cA'IQxN
Stable
def bubbleSort(c, n):
    flag = 1
    while(flag) :
        flag = 0
        for i in reversed(range(1,n)):
            if(c[i][1] < c[i-1][1]):
                c[i], c[i-1] = c[i-1], c[i]
                flag = 1
    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):
    for i in range(n):
        if(c1[i] != c2[i]):
            return False
    return True

n = int(input())
c = input().split(' ')
trump = [list(i) for i in c]
bubble = ["".join(s) for s in bubbleSort(trump, n)]
trump = [list(i) for i in c]
selection = ["".join(s) for s in selectionSort(trump, n)]
str_bubble = " ".join(bubble)
str_selection = " ".join(selection)
print(str_bubble)
print('Stable')
print(str_selection)
if isStable(bubble, selection, n):
    print('Stable')
else:
    print('Not stable')



# Example run
# Input:
0
d]lv%m)k
# Output:
d]lv%m)k
Stable
d]lv%m)k
Stable
class Bubblesort():
    def __init__(self,x,n):
        self.C = x
        self.n = n
    def sorting(self):
        for i in range(self.n):
            for j in range(self.n - 1 , i , -1):
                if int(self.C[j][1]) < int(self.C[j - 1][1]):
                    self.C[j], self.C[j - 1] = self.C[j - 1], self.C[j]
        return self.C
    
    def check(self, xx):
        return CheckStable(self.C, xx)

class Selectionsort():
    def __init__(self, x, n):
        self.C = x
        self.n = n
    def sorting(self):
        for i in range(0, self.n):
            minj = i
            for j in range(i+1, self.n):
                if int(self.C[j][1])  < int(self.C[minj][1]):
                    minj = j
            self.C[i], self.C[minj] = self.C[minj], self.C[i]
        return self.C
    
    def check(self, xx):
        return CheckStable(self.C, xx)
    
def CheckStable(x1, xx2):
    ch1 = []
    for i in range(n - 1):
        if x1[i][1] == x1[i + 1][1]:
            ch1.append(x1[i])
            if i + 1 == n - 1:
                ch1.append(x1[i + 1])
        elif x1[i - 1][1] == x1[i][1]:
            ch1.append(x1[i])
    
    ch2 = []
    x2 = xx2
    for i in ch1:
        for j in range(len(x2)):
            if i[1] == x2[j][1]:
                ch2.append(x2[j])
                x2.pop(j)
                break

    if ch1 == ch2:
        return ('Stable')
    else:
        return ('Not stable')

n = int(input())
x = input().split()
xx =x[:]
y =x[:]
yy =x[:]

a = Bubblesort(x, n)
b = Selectionsort(y, n)
print(' '.join(a.sorting()))
print(a.check(xx))
print(' '.join(b.sorting()))
print(b.check(yy))


# Example run
# Input:
-17367
k^C
# Output:
k^C
Stable
k^C
Stable
N = int(input())
C = input().split()
_C = C.copy()

for i in range(N):
    for j in range(N-1, i, -1):
        if (C[j] < C[j-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] < _C[j-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:
-6940
DP\@LU%V
# Output:
DP\@LU%V
Stable
DP\@LU%V
Stable
def bubbleSort(A,N):
    flag = 1
    count = 0
    while flag:
        flag = 0
        for j in range(N-1,0,-1):
            Aj = int(A[j][1])
            Aj_1 = int(A[j-1][1])
            if Aj < Aj_1:
                A[j],A[j-1] = A[j-1],A[j]
                flag = 1
                count += 1
    return A[:]

def selectionSort(A,N):
    count=0
    for i in range(N):
        minj = i
        for j in range(i,N):
            Aj = int(A[j][1])
            Aminj = int(A[minj][1])
            if Aj < Aminj:
                minj = j
        A[i],A[minj] = A[minj],A[i]
        if i != minj:
            count +=1
    return A[:]

N = int(input())
#table = input().split()
#for c in range(input().split()):
#    l.append(int(c[1],c[0]))
table = [x for x in input().split(' ')]
t = table[:]
u = table[:]
#B = A.copy

A=bubbleSort(t,N)
print('{0}'.format(' '.join(map(str,A))))
print('Stable')
B=selectionSort(u,N)
print('{0}'.format(' '.join(map(str,B))))
if A == B:
    print('Stable')
else:
    print('Not stable')



# Example run
# Input:
-1523
VW[.#h"0&
# Output:
VW[.#h"0&
Stable
VW[.#h"0&
Stable
n = int(input())
bLst = input().split()
iLst = bLst

for i in range(n):
    for j in range(n-1,i,-1):
        if bLst[j][1] < bLst[j-1][1]:
            bLst[j],bLst[j-1] = bLst[j-1],bLst[j]

print(*bLst)
print("Stable")

for i in range(n):
    min = i
    for j in range(i,n):
        if iLst[j][1] < iLst[min][1]:
            min = j
    iLst[i],iLst[min] = iLst[min],iLst[i]

print(*iLst)
if bLst == iLst:
    print("Stable");
else:
    print("Not stable")


# Example run
# Input:
-1
hd](
# Output:
hd](
Stable
hd](
Stable
import copy
N = int(input())
Cards1 = list(map(str, input().split()))
# リストのコピー
# copyをインポートしてcopy.deepcopy()関数を使う。
Cards2 = copy.deepcopy(Cards1)


# バブルソート: Cards1
for i in range(0, N):
    for j in reversed(range(i+1, N)):
        if int(Cards1[j][1:]) < int(Cards1[j-1][1:]):
            Cards1[j], Cards1[j-1] = Cards1[j-1], Cards1[j]

# 選択ソート: Cards2
for i in range(0, N):
    minj = i
    for j in range(i, N):
        if int(Cards2[j][1:]) < int(Cards2[minj][1:]):
            minj = j
    Cards2[i], Cards2[minj] = Cards2[minj], Cards2[i]

print(*Cards1)
print('Stable')
print(*Cards2)
if Cards1 != Cards2:
    print('Not stable')
else:
    print('Stable')

# バブルソートは安定ソート
# 選択ソートは安定ソートではない



# Example run
# Input:
-59158
cQG
# Output:
cQG
Stable
cQG
Stable
def main():
    n = int(input())
    cards = list(map(str, input().split()))
    bubbleSortedCards = cards[:]
    selectionSortedCards = cards[:]


    bubbleSort(bubbleSortedCards, n)
    print(' '.join(map(str, bubbleSortedCards)))
    print('Stable')

    selectionSort(selectionSortedCards, n)
    print(' '.join(map(str, selectionSortedCards)))
    print(isStable(bubbleSortedCards, selectionSortedCards, n))


def bubbleSort(numbers, n):
    for i in range(n - 1, 0, -1):
        for j in range(i):
            if int(numbers[j][1]) > int(numbers[j + 1][1]):
                numbers[j], numbers[j + 1] = numbers[j + 1], numbers[j]

def selectionSort(numbers, n):
    minj = 0

    for i in range(n):
        minj = i
        for j in range(i, n, 1):
            if int(numbers[j][1]) < int(numbers[minj][1]):
                minj = j

        if i != minj:
            numbers[i], numbers[minj] = numbers[minj], numbers[i]

def isStable(bubbleSortedCards, selectionSortedCards, n):
    for i in range(n):
        if bubbleSortedCards[i] != selectionSortedCards[i]:
            return 'Not stable'

    return 'Stable'

if __name__ == '__main__':
    main()



# Example run
# Input:
-4
GE(ah
# Output:
GE(ah
Stable
GE(ah
Stable
#安定なソート
N = int(input())
*A, = input().split()

def stableSort(N,A):
    cnum1 = [(a[0], int(a[1:])) for a in A]
    
    #バブルソート
    flag = 1
    i = 0
    while i < N-1:
        for j in range(N-1, i, -1):
            if cnum1[j][1] < cnum1[j-1][1]:
                tmp = cnum1[j]
                cnum1[j] = cnum1[j-1]
                cnum1[j-1] = tmp
        i += 1
    print(' '.join([''.join([cn[0], str(cn[1])]) for cn in cnum1]))
    print('Stable')
    
    #選択ソート
    cnum2 = [(a[0], int(a[1:])) for a in A]
    count = 0
    for i in range(N):
        minj = i
        for j in range(i+1, N):
            if cnum2[j][1] < cnum2[minj][1]:
                minj = j
        if not minj == i:
            tmp = cnum2[i]
            cnum2[i] = cnum2[minj]
            cnum2[minj] = tmp
            count += 1
    print(' '.join([''.join([cn[0], str(cn[1])]) for cn in cnum2]))
    print('Not stable' if cnum1 != cnum2 else 'Stable' )

stableSort(N,A)
    


# Example run
# Input:
-236540
4484588
# Output:
4484588
Stable
4484588
Stable
def do_bubble_sort(data, n):
    """ ??°???data??????????????????????????????????????§???????????????????????????n?????°????????????
    ?????????????????????????????°??¨????????????????????????????????????
    """
    flag = True
    i = 0
    while flag is True:
        flag = False
        for j in range(n-1, i, -1):
            dj = int(data[j][1])
            dj_1 = int(data[j-1][1])
            #if data[j] < data[j-1]:
            if dj < dj_1:
                temp = data[j]
                data[j] = data[j-1]
                data[j-1] = temp
                flag = True
        i == 1
    return



def do_selection_sort(data, size):
    assert size == len(data), "data size error"
    for i in range(size):
        minj = i
        for j in range(i, size):
            dj = int(data[j][1])
            dmin = int(data[minj][1])
            if dj < dmin:
            #if data[j] < data[minj]:
                minj = j
        temp = data[i]
        data[i] = data[minj]
        data[minj] = temp
    return


def is_stable(bubble_d, selection_d):
    for b, s in zip(bubble_d, selection_d):
        if b != s:
            return False
    return True


if __name__ == '__main__':
    # ??????????????\???
    num = int(input())
    cards = [x for x in input().split(' ')]
    #cards = ['H4', 'C9', 'S4', 'D2', 'C3']
    #cards = ['S1', 'H1']
    t = cards[:]  # ???????????????
    u = cards[:]

    # ???????????????????????????
    do_bubble_sort(t, len(t))
    do_selection_sort(u, len(u))
    result = is_stable(t, u)

    # ???????????????
    print('{0}'.format(' '.join(map(str, t))))
    print('Stable')
    print('{0}'.format(' '.join(map(str, u))))
    if result is True:
        print('Stable')
    else:
        print('Not stable')

# Example run
# Input:
56
-2
# Output:
-2
Stable
-2
Stable