Felix6326727/beyond-accuracy-code-comprehension huggingface dataset:
import copy

def bubble(N, A):
    for i in range(N - 1):
        for j in reversed(range(1, N)):
            if A[j - 1][1] > A[j][1]:
                tmp = A[j]
                A[j] = A[j - 1]
                A[j - 1] = tmp

def select(N, A):
    for i in range(N):
        min = i
        for j in range(i, N):
            if A[min][1] > A[j][1]:
                min = j
        tmp = A[i]
        A[i] = A[min]
        A[min] = tmp

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

N = int(input())
#カード入力
S = [i for i in input().split()]
B = copy.deepcopy(S)

bubble(N, B)
select(N, S)

print(" ".join(B))
print("Stable")
print(" ".join(S))
if st(B, S) == True:
    print("Stable")
else:
    print("Not stable")


# Example run
# Input:
-213058
kmQ3
# Output:
kmQ3
Stable
kmQ3
Stable
# Stable Sort

n = int(input())
C = list(input().split(' '))

C1, C2 = [], []
for v in C:
	tmp = v[0]
	num = int(v[1])
	C1.append([tmp, num])
	C2.append([tmp, num])

def bubble(A):
	n = len(A)
	for i in range(n):
		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]
	return 0

def selection(A):
	n = len(A)
	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]
	return 0

def is_Stable(C1, C2):
	# bubble sort is always stable
	n = len(C1)
	for i in range(n):
		if C1[i][0] != C2[i][0]:
			return False
	return True

def pprint(A):
	res = []
	for v in A:
		tmp1 = v[0]
		tmp2 = str(v[1])
		res.append(tmp1 + tmp2)
	print(*res)
	return
	
bubble(C1)
selection(C2)

pprint(C1)
print('Stable')
pprint(C2)
print('Stable') if is_Stable(C1, C2) else print('Not stable')



# Example run
# Input:
-9
89
# Output:
89
Stable
89
Stable
N = int(input()) 
C = list(input().split())
C1 = C[:]
C2 = C[:]

def func(C):
    nums = []
    for i in range(N-1):
        for j in range(i+1,N):
            if C[i][1] in nums:
                continue
            elif C[i][1] == C[j][1]:
                nums.append(C[i][1])
    nums.sort()

    test = []
    for i in range(len(nums)):
        A = []
        for j in range(N):
            if C[j][1] == nums[i]:
                A.append(C[j])
        test.append(A)
    return test

def isStable(A,B):
    if func(A) == func(B):
        print("Stable")
    else:
        print("Not stable")

for i in range(N):
    for j in range(N-1,i,-1):
        if int(C1[j][1]) < int(C1[j-1][1]):
            C1[j],C1[j-1] = C1[j-1],C1[j]
print(*C1)
isStable(C,C1)

for i in range(N):
    minj = i
    for j in range(i,N):
        if int(C2[j][1]) < int(C2[minj][1]):
            minj = j
    C2[i],C2[minj] = C2[minj],C2[i]
print(*C2)
isStable(C,C2)


# Example run
# Input:
-997466
VdH
# Output:
VdH
Stable
VdH
Stable
import copy
num = int(input())
base_list = list(input().split())
a = copy.copy(base_list)
b = copy.copy(base_list)

for i in range(num):
    for j in reversed(range(i+1,num)):
        if a[j][1] < a[j-1][1]:
            a[j],a[j-1] = a[j-1],a[j]

print(" ".join([str(i) for i in a]))
print('Stable')

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

print(" ".join([str(i) for i in b]))
flg = False
for bubble,sele in zip(a,b):
    if bubble != sele:
        flg = True
        break

if flg:
    print('Not stable')
else:
    print('Stable')



# Example run
# Input:
-5271130
Og\?C
# Output:
Og\?C
Stable
Og\?C
Stable
n=int(input())
lst=list(input().split())
lst1=[""]*n
lst2=[""]*n
for i in range(n):
    lst1[i]=lst[i]
    lst2[i]=lst[i]

for i in range(n-1):
    for j in range(i+1,n)[::-1]:
        if int(lst1[j][1])<int(lst1[j-1][1]):
            lst1[j],lst1[j-1]=lst1[j-1],lst1[j]
print(*lst1)
print("Stable")

for i in range(n-1):
    minlst=min([int(lst2[_][1]) for _ in range(i,n)])
    if minlst==int(lst2[i][1]):continue
    for j in range(i+1,n):
        if minlst==int(lst2[j][1]):
            lst2[i],lst2[j]=lst2[j],lst2[i]
            break
print(*lst2)
print("Stable" if lst1==lst2 else "Not stable")


# Example run
# Input:
-112
Z0G;pgH
# Output:

Stable

Stable
class Selection_sort:
    def __init__(self):
        self.swap_num=0
    
    def sort(self,data):
        for i in range(len(data)):
            mini=i
            for j in range(i+1,len(data)):
                if(data[j][1] < data[mini][1]):
                    mini=j
            if(mini!=i):
                data[i],data[mini]=data[mini],data[i]
                self.swap_num+=1


class Bubble_sort:
    def __init__(self):
        self.swap_num=0
    
    def sort(self,list):
        for i in range(len(list)):
            for j in range(i+1,len(list))[::-1]:
                if(list[j][1] < list[j-1][1]):
                    list[j],list[j-1]=list[j-1],list[j]
                    self.swap_num+=1


def stability_judge(sorted,original):
    n=len(sorted)
    j=-1
    x=sorted[0][1]
    for i in range(n):
        if(x!=sorted[i][1]):
            x=sorted[i][1]
            j=-1
        
        while(1):
            j+=1
            if(x==original[j][1]):
                if(sorted[i][0]!=original[j][0]):
                    return 0
                else:
                    break
    return 1


def cards_print(cards):
    newcards=[]
    for card in cards:
        card[1]=str(card[1])
    newcards=["".join(card) for card in cards]    
    print(" ".join(newcards))




n=int(input())
cards=[list(str) for str in input().split()]
for card in cards:
    card[1]=int(card[1])

b_cards=[i for i in cards]
s_cards=[i for i in cards]


bubble_sort=Bubble_sort()
bubble_sort.sort(b_cards)
#x=stability_judge(b_cards,cards)
cards_print(b_cards)

if(stability_judge(b_cards,cards)):
    print("Stable")
else:
    print("Not stable")



selection_sort=Selection_sort()
selection_sort.sort(s_cards)
cards_print(s_cards)
if(stability_judge(s_cards,cards)):
    print("Stable")
else:
    print("Not stable")


# Example run
# Input:
31481447
-85068029
# Output:
-85068029
Stable
-85068029
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

def isStable(inA, out):
    for i in range(0, n):
        for j in range(i+1, n):
            for a in range(0, n):
                for b in range(a+1, n):
                    if inA[i][1] == inA[j][1] and inA[i] == out[b] and inA[j] == out[a]:
                        return "Not Stable"
    return "Stable"



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

B = bubble(A[:])
print(" ".join(B))
print(isStable(A, B))
S = select(A[:])
print(" ".join(S))
print(isStable(A, S))

# Example run
# Input:
-30
YQocc[TJS
# Output:
YQocc[TJS
Stable
YQocc[TJS
Stable
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:
            #times += 1
        A[i], A[minj] = A[minj], A[i]
        #print(*A)
    return A

def BubbleSort(A, N):
    for i in range(N):
        for j in reversed(range(i+1, N)):
            if A[j][1:] < A[j-1][1:]:
                A[j], A[j-1] = A[j-1], A[j]

    return A

N= int(input())
A = [str(x) for x in input().split()]
B = [0 for i in range(N)]
for i in range(N):
    B[i] = A[i]
bubble = BubbleSort(A, N)
selection = SelectionSort(B, N)
#print(A, B)
#print(*A)
print(*bubble)
print('Stable')
print(*selection)
if bubble == selection:
    print('Stable')
else:
    print('Not stable')

# Example run
# Input:
-7
\&s
# Output:
\&s
Stable

Not stable
from collections import namedtuple
C = namedtuple("C", "m v")


def bubble_sort(A0):
    A = A0.copy()
    for i in range(n - 1):
        for j in range(n - 1, i, -1):
            if A[j].v < A[j - 1].v:
                A[j], A[j - 1] = A[j - 1], A[j]
    return A, True


def selection_sort(A0):
    A = A0.copy()
    for i in range(n - 1):
        k = i
        for j in range(i + 1, n):
            if A[k].v > A[j].v:
                k = j
        if k != i:
            A[k], A[i] = A[i], A[k]
    return A


lst = ["Not stable", "Stable"]
n = int(input())
A = [C(x[0], x[1]) for x in input().split()]

B, j = bubble_sort(A)
print(*[(B[i].m + B[i].v) for i in range(n)])
print(lst[j])

S = selection_sort(A)
print(*[(S[i].m + S[i].v) for i in range(n)])
print(lst[B == S])



# Example run
# Input:
-1138
HdbM
# Output:

Stable

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

    def __eq__(self, other):
        if not isinstance(other, Card):
            return NotImplemented
        return self.value == other.value and self.mark == other.mark

    def __lt__(self, other):
        return self.value < other.value

    def __str__(self):
        return self.mark + str(self.value)


def BubbleSort(arr):
    res = [Card(c.mark, c.value) for c in arr]
    swap_flg = True
    i = 0
    while swap_flg:
        swap_flg = False
        for j in range(len(res) - 1, i, -1):
            if (res[j] < res[j - 1]):
                res[j], res[j - 1] = res[j - 1], res[j]
                swap_flg = True
        i += 1
    return res


def SelectionSort(arr):
    res = [Card(c.mark, c.value) for c in arr]
    for i in range(0, len(res)):
        minj = i
        for j in range(i, N):
            if res[j] < res[minj]:
                minj = j
        if (i != minj):
            res[i], res[minj] = res[minj], res[i]
    return res


def isStable(in_arr, out_arr):
    stable_arr = BubbleSort(in_arr)
    return all(out_arr[i] == stable_arr[i] for i in range(0, len(out_arr)))


N = int(input())
arr = [Card(s[0], int(s[1])) for s in input().split()]
b_arr = BubbleSort(arr)
print(' '.join(map(str, b_arr)))
print('Stable' if isStable(arr, b_arr) else 'Not stable')
s_arr = SelectionSort(arr)
print(' '.join(map(str, s_arr)))
print('Stable' if isStable(arr, s_arr) else 'Not stable')



# Example run
# Input:
-185685
1419428
# Output:
14
Stable
14
Stable
import copy
def BubbleSort(n, A):
    cnt = 0
    flg = True
    while flg:
        flg = False
        for j in range(n-1, 0, -1):
            if int(A[j][1:2]) < int(A[j-1][1:2]):
                tmp = A[j]
                A[j] = A[j-1]
                A[j-1] = tmp
                cnt += 1
                flg = True
    
def SelectionSort(n, B):
    cnt = 0
    for i in range(n):
        minj = i
        for j in range(i+1, n):
            if int(B[j][1:2]) < int(B[minj][1:2]):
                minj = j
        if minj != i:
            tmp = B[i]
            B[i] = B[minj]
            B[minj] = tmp
            cnt += 1
    
def IsStable(A, B):
    for a1 in A:
        for b1 in B:
            if int(a1[1:2]) == int(b1[1:2]):
                if a1 == b1:
                    B.remove(b1)
                    break
                else:
                    return "Not stable"
            elif int(a1[1:2]) < int(b1[1:2]):
                break
    return "Stable"
    
n = int(input())
C = input().split()
A = copy.deepcopy(C)
B = copy.deepcopy(C)

BubbleSort(n, A)
print(" ".join(A))
print(IsStable(C, A))

SelectionSort(n, B)
print(" ".join(B))
print(IsStable(C, B))


# Example run
# Input:
0
-14
# Output:
-14
Stable
-14
Stable
_, cards = input(), input().split()

def bubble_sort(array):
    A = array[:]
    for i in range(len(A)):
        for j in range(1, len(A) - i):
            if int(A[j - 1][1]) > int(A[j][1]):
                A[j], A[j - 1] = A[j - 1], A[j]
    return A

def selection_sort(array):
    A = array[:]
    for i in range(len(A)):
        minn = i
        for j in range(i, len(A)):
            if int(A[j][1]) < int(A[minn][1]): minn = j
        A[i], A[minn] = A[minn], A[i]
    return A
def is_stable(org, sorted):

    def get_same_numbers(array):
        result = {}
        for i in range(1, 10):
            result[i] = []
            for j in range(len(array)):
                if int(array[j][1]) == i:
                    result[i].append(array[j])
        return [cards for _, cards in result.items() if len(cards) >= 2]

    return "Stable" if get_same_numbers(org) == get_same_numbers(sorted) else "Not Stable"

a = bubble_sort(cards)
print(" ".join(a))
print(is_stable(cards, a))
b = selection_sort(cards)
print(" ".join(b))
print(is_stable(cards, b))


# Example run
# Input:
bseXf?
38254
# Output:
38254
Stable
38254
Stable
# -*- coding:utf-8 -*-

def Selection_Sort(A,n):
    for i in range(n):
        mini = i
        for j in range(i,n): #i以上の要素において最小のAをminiに格納
            if int(A[j][1]) < int(A[mini][1]):
                mini = j
        if A[i] != A[mini]:
            A[i], A[mini] = A[mini], A[i]
    return A
    
def Bubble_Sort(A, n):
    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
    
n = int(input())
A = input().strip().split()

B = A[:]
A = Bubble_Sort(A,n)
print (' '.join(A))
print ("Stable")
B =Selection_Sort(B,n)
print (' '.join(B))

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

# Example run
# Input:
-97071
Zz}.
# Output:
Zz}.
Stable
Zz}.
Stable
import copy
n = int(input())
a = list(map(str, input().split()))
a_buble = copy.copy(a)
for i in range(n):
  for j in range(n-1,i,-1):
    if int(a_buble[j][1]) < int(a_buble[j-1][1]):
      temp = a_buble[j]
      a_buble[j] =a_buble[j-1]
      a_buble[j-1] = temp
      
print(" ".join(map(str,a_buble)))
print("Stable")

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
  temp = a[i]
  a[i] = a[minj]
  a[minj] = temp
print(" ".join(map(str,a)))
ans = "Stable"
for k in range(n):
  if a[k] != a_buble[k]:
    ans = "Not stable"
print(ans)



# Example run
# Input:
0
t#:3
# Output:
t#:3
Stable
t#:3
Stable
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_C&lang=jp
#??????????????????
#??????????????????????°???????????????£?????´???????????´?????¨??\?????????????????????????????????????????´????????????
#??????????????????????????????????°????????????????????????´???????????????????????????????????????????????¨??????

def bubble_sort(origin_list):
    list_length = len(origin_list)
    target_list = [i for i in origin_list]#??°????????????????????????
    flag = True
    change_count = 0
    top_index = 1
    while flag:
        flag = False
        for i in range(top_index, list_length)[::-1]:
            if target_list[i][1] < target_list[i - 1][1]:
                tmp = target_list[i]
                target_list[i] = target_list[i - 1]
                target_list[i - 1] = tmp
                change_count += 1
                flag = True
        top_index += 1       
    return target_list

def selection_sort(origin_list):
    list_length = len(origin_list)
    target_list = [i for i in origin_list]#??°????????????????????????
    change_count = 0
    for i in range(list_length):
        min_index = i
        for j in range(i, list_length):
            if target_list[j][1] < target_list[min_index][1]:
                min_index = j
        else:
            if not i == min_index:
                tmp = target_list[i]
                target_list[i] = target_list[min_index]
                target_list[min_index] = tmp
                change_count += 1
    return target_list

def check_stable(origin_list, target_list):
    for i, origin_v in enumerate(origin_list):
        for origin_v2 in origin_list[i+1:]:
            if origin_v[1] == origin_v2[1]:
                for j, target_v in enumerate(target_list):
                    for target_v2 in target_list[j+1:]:
                        if origin_v == target_v2 and origin_v2 == target_v:
                            return "Not stable"
    return "Stable"

def stable_sort(target_list):
    print(*bubble_sort(target_list))
    print(check_stable(target_list, bubble_sort(target_list)))
    print(*selection_sort(target_list))
    print(check_stable(target_list, selection_sort(target_list)))
    
def main():
    n_list = int(input())
    target_list = [a for a in input().split()]
    stable_sort(target_list)
    
if __name__ == "__main__":
    main()

# Example run
# Input:
3320259
+^6
# Output:
+^6
Stable
+^6
Stable
def bubble_sort(A,N):
    for i in range(N):
        for j in range(N-1,i+1-1,-1):
            if int(A[j][1:])<int(A[j-1][1:]):
                A[j],A[j-1] = A[j-1],A[j]
    return A    

def selection_sort(A,N):
    for i in range(N):
        minj = i
        for j in range(i+1,N):
            if int(A[j][1:])<int(A[minj][1:]):
                minj = j
        if minj != i:
            A[minj],A[i] = A[i],A[minj]
    return A
    
N = int(input())
A = input().split()

A_bubble = bubble_sort(A.copy(), N)
A_select = selection_sort(A.copy(), N)

print(*A_bubble)
print('Stable')
print(*A_select)
if A_select == A_bubble:
    print('Stable')
else:
    print('Not stable')


# Example run
# Input:
-7149041
UIV5~J;T
# Output:
UIV5~J;T
Stable
UIV5~J;T
Stable
import copy

n = int(input())
arr1 = [(int(x[-1]), x) for x in list(input().split())]
arr2 = copy.copy(arr1)

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

def select_sort(arr, n):
  for i in range(n):
    minj = i
    for j in range(i, n):
      if arr[j][0] < arr[minj][0]:
        minj = j
    arr[i],arr[minj] = arr[minj],arr[i]

def check_stable(input, output):
  return 'Stable' if input == output else 'Not stable'

def arr_to_map(input):
  return ' '.join([x[1] for x in input])

bubble_sort(arr1, n)
select_sort(arr2, n)

print (arr_to_map(arr1))
print ('Stable')
print (arr_to_map(arr2))
print (check_stable(arr1, arr2))


# Example run
# Input:
-76577
-1069713
# Output:
-1069713
Stable
-1069713
Stable
import copy

N = int(input())

def hoge(arg):
    return [arg[0], int(arg[1])]

A = list(map(hoge, map(str, input().split())))
A1 = copy.deepcopy(A)
A2 = copy.deepcopy(A)

def bsort(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]

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

def judge(A, A1):
    for i in range(len(A) - 1):
        if A1[i][1] != A1[i+1][1]:
            continue
        a = A.index(A1[i])
        b = A.index(A1[i+1])
        if a > b:
            return 'Not stable'
    return 'Stable'

def toString(A):
    return A[0] + str(A[1])

bsort(A1, N)
print(' '.join(list(map(toString, A1))))
print(judge(A, A1))
ssort(A2, N)
print(' '.join(list(map(toString, A2))))
print(judge(A, A2))



# Example run
# Input:
-2147483648
283975609
# Output:
28
Stable
28
Stable
N = int(input())

C = input().split()

B = C[:]
S = C[:]

# bubble sort
flag = 1
while(flag):
    flag = 0
    for x in range(1, N):
        if B[x][1:] < B[x-1][1:]:
            B[x], B[x-1] = B[x-1], B[x]
            flag = 1

# sectionSot
for x in range(0,N):
    minj = x
    for j in range(x,N):
        if S[j][1:] < S[minj][1:]:
            minj = j
    if minj != x:
        S[x], S[minj] = S[minj], S[x]

for i in range(1, N):
    v = C[i]
    j = i - 1
    while(j >=0 and C[j][1:] > v[1:]):
        C[j+1] = C[j]
        j -= 1
    C[j+1] = v

if(C == B):
    print(" ".join(b for b in B))
    print("Stable")
else:
    print(" ".join(b for b in B))
    print("Not stable")


if(C == S):
    print(" ".join(b for b in S))
    print("Stable")
else:
    print(" ".join(b for b in S))
    print("Not stable")

# Example run
# Input:
-296641124
oau}Q!*
# Output:
oau}Q!*
Stable
oau}Q!*
Stable
def str_selection_sort(a,n):
    m=0
    for i in range(0,n):
        minj=i
        for j in range(i,n):
            if(int(a[minj][1:]) > int(a[j][1:])):
                minj=j
        if(minj!=i):
            m+=1
            a[minj],a[i] = a[i],a[minj]
        
    print(" ".join(a))
    return a

def str_bubble_sort(a,n):
    m=0
    flag=True
    while(flag):
        flag=False
        for i in range(n-1,0,-1):
            if(a[i-1][1:] > a[i][1:]):
                tmp=a[i-1]
                a[i-1]=a[i]
                m+=1
                a[i]=tmp
                flag=True
                
    print(" ".join(a))
    return a

def is_stable(a,b,n):
    for i in range(1,n):
        if(b[i-1][1:]!=b[i][1:]):
            continue
        flag=False
        for j in a:
            if(j[:1]==b[i-1][:1] and (not flag)):
                flag=True
                continue
            if(j[:1]==b[i][:1]):
                if(not flag):
                    return False
                else:
                    return True
        
        if(flag):
            return False
    return True

a=[]
n=int(input())
s=input()
a=s.split()
b=str_bubble_sort(list(a),n)
if(is_stable(a,b,n)):
    print("Stable")
else:
    print("Not stable")
b=str_selection_sort(list(a),n)
if(is_stable(a,b,n)):
    print("Stable")
else:
    print("Not stable")

# Example run
# Input:
0
\`J8'OrS
# Output:
\`J8'OrS
Stable
\`J8'OrS
Stable
def isStable(in_lst,out_lst):
    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 in_lst[i][1] == in_lst[j][1] and in_lst[i] == out_lst[b] and in_lst[j] == out_lst[a]:
                        return False
    return True

def isStable1(in_lst,out_lst):
    tmp = isStable(in_lst,out_lst)
    if tmp == True:
        print('Stable')
    else:
        print('Not stable')

n = int(input())
lst = list(map(str,input().split()))
ans_lst = lst.copy()
for i in range(0,n):
    for j in range(n-1,i,-1):
        if lst[j][1] < lst[j-1][1]:
            lst[j],lst[j-1] = lst[j-1],lst[j]

print(' '.join(lst))
isStable1(ans_lst,lst)

lst = ans_lst.copy()
for i in range(n):
    minj = i
    for j in range(i,n):
        if lst[j][1] < lst[minj][1]:
            minj = j
    lst[i],lst[minj] = lst[minj],lst[i]

print(' '.join(lst))
isStable1(ans_lst,lst)






# Example run
# Input:
-239
h-dj
# Output:
h-dj
Stable
h-dj
Stable
import copy

def bubble(N, A):
    for i in range(N - 1):
        for j in reversed(range(1, N)):
            if A[j - 1][1] > A[j][1]:
                tmp = A[j]
                A[j] = A[j - 1]
                A[j - 1] = tmp

def select(N, A):
    for i in range(N):
        min = i
        for j in range(i, N):
            if A[min][1] > A[j][1]:
                min = j
        tmp = A[i]
        A[i] = A[min]
        A[min] = tmp

def st(B, S):
    for i in range(N):
        if B[i] == S[i]:
            return False
    return True

N = int(input())
#カード入力
S = [i for i in input().split()]
B = copy.deepcopy(S)

bubble(N, B)
select(N, S)

print(" ".join(B))
print("Stable")
print(" ".join(S))
if st(B, S) == True:
    print("Stable")
else:
    print("Not Stable")


# Example run
# Input:
-1
WL]
# Output:
WL]
Stable
WL]
Stable