Felix6326727/beyond-accuracy-code-comprehension huggingface dataset:
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]
    return A

def BubbleSort(A, N):
    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 A

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

# Example run
# Input:
-25166
j9Bc
# Output:
j9Bc
Stable
j9Bc
Stable
def bubleSort(table):
    table = table.copy()
    for nAchieve in range(len(table)):
        for i in range(len(table) - 1, nAchieve, -1):
            if table[i][1] < table[i - 1][1]:
                table[i], table[i - 1] = table[i - 1], table[i]
    return table


def selectionSort(table):
    table = table.copy()
    for nAchieve in range(len(table)):
        minimum_index = nAchieve
        for i in range(nAchieve + 1, len(table)):
            if table[minimum_index][1] > table[i][1]:
                minimum_index = i
        if minimum_index != nAchieve:
            table[nAchieve], table[minimum_index] = table[minimum_index], table[nAchieve]
    return table


def checkStable(stable, comparison):
    if stable == comparison:
        return 'Stable'
    else:
        return 'Not stable'


element = int(input())
table = list(map(str, input().split()))

y = selectionSort(table)
x = bubleSort(table)
print(' '.join(map(str, x)))
print('Stable')
print(' '.join(map(str, y)))
print(checkStable(x, y))



# Example run
# Input:
82157
O.eIJW<
# Output:
O.eIJW<
Stable
O.eIJW<
Stable
import copy
N = int(input())
A = [[i for i in item] for item in input().split()]

B = copy.deepcopy(A)

def bubbleSort(A, N):
    for i in range(N):
        for i in reversed(range(i, N-1)):
            if A[i][1] > A[i+1][1]:
                A[i], A[i+1] = A[i+1], A[i]

    res = []
    for item in A:
        temp_res = ''
        for i in item:
            temp_res += i
        res.append(temp_res)
    return res



def selectionSort(A, N):
    cnt = 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:
            A[i], A[minj] = A[minj], A[i]
    
    res = []
    for item in A:
        temp_res = ''
        for i in item:
            temp_res += i
        res.append(temp_res)
    return res

A_res = bubbleSort(A, N)
B_res = selectionSort(B, N)

print(*A_res)
print('Stable')
print(*B_res)
if A_res == B_res:
    print('Stable')
else:
    print('Not stable')


# Example run
# Input:
-675765611
"O?Wixhv
# Output:
"O?Wixhv
Stable
"O?Wixhv
Stable
class Card():
    def __init__(self, suit, value):
        self.suit = suit
        self.value = value

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

def ChkIfStable(c1, c2):
    for v in range(1,10):
        a1=[]
        for k1 in c1:
            if k1.value == v: a1.append(k1.suit)
        a2=[]
        for k2 in c2:
            if k2.value == v: a2.append(k2.suit)
        if a1!=a2:
            print('Not stable')
            return
    print('Stable')

def BubbleSort(C):
    for i in range(0, len(C)):
        for j in range(len(C)-1,i,-1):
            if C[j].value < C[j-1].value:
                 C[j], C[j-1] = C[j-1], C[j]
    return C

def SelectionSort(C):
    for i in range(len(C)):
        mini = i
        for j in range(i, len(C)):
            if C[j].value < C[mini].value:
                mini = j
        C[i], C[mini] = C[mini], C[i]
    return C

cc = []
input()
for c in input().split():
    cc.append(Card(c[0], int(c[1])))

bs=BubbleSort(cc[:])
print(' '.join(map(str,bs)))
ChkIfStable(cc, bs)
ss=SelectionSort(cc[:])
print(' '.join(map(str,ss)))
ChkIfStable(cc, ss)


# Example run
# Input:
BFR
23
# Output:
23
Stable
23
Stable
from typing import List


def get_value(card: str) -> int:
    return card[1]


def bublle_sort(C: List[str]) -> None:
    for i in range(len(C)):
        for j in reversed(range(i + 1, len(C))):
            if get_value(C[j]) < get_value(C[j - 1]):
                C[j], C[j - 1] = C[j - 1], C[j]


def selection_sort(C: List[str]) -> None:
    for i in range(len(C)):
        min_j = i
        for j in range(i, len(C)):
            if get_value(C[j]) < get_value(C[min_j]):
                min_j = j
        C[i], C[min_j] = C[min_j], C[i]


def is_stable(A_in, A_out) -> bool:
    for i in range(len(A_in)):
        for j in range(i + 1, len(A_in)):
            for a in range(len(A_out)):
                for b in range(a + 1, len(A_out)):
                    if get_value(A_in[i]) == get_value(A_in[j]) and A_in[i] == A_out[b] and A_in[j] == A_out[a]:
                        return False
    return True


N = int(input())
C = [str(i) for i in input().split()]
C1 = [i for i in C]
C2 = [i for i in C]

bublle_sort(C1)
print(' '.join(C1))
if is_stable(C, C1):
    print('Stable')
else:
    print('Not stable')

selection_sort(C2)
print(' '.join(C2))
if is_stable(C, C2):
    print('Stable')
else:
    print('Not stable')



# Example run
# Input:
-76824657
Js>o<w]
# Output:
Js>o<w]
Stable
Js>o<w]
Stable
from operator import lt

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

    Ab = bubbleSort(A[:], N, lambda a, b: int(a[1]) < int(b[1]))
    As = selectionSort(A[:], N, lambda a, b: int(a[1]) < int(b[1]))

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

    print(' '.join([str(a) for a in As]))
    print('Stable' if Ab == As else 'Not stable')

def bubbleSort(A, N, comp=lt):
    flag = True

    while flag:
        flag = False

        for j in range(N-1, 0, -1):
            if comp(A[j], A[j-1]):
                A[j], A[j-1] = A[j-1], A[j]
                flag = True

    return A

def selectionSort(A, N, comp=lt):
    for i in range(0, N-1):
        minj = i

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

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

    return A

if __name__ == '__main__':
    main()

# Example run
# Input:
-56
qy@Q$2^1
# Output:
qy@Q$2^1
Stable
qy@Q$2^1
Stable
def BubbleSort(A):
    loop = len(A)-1
    for i in range(loop):
        for j in range(loop-i):
            if A[j][1] > A[j+1][1]:
                A[j],A[j+1] = A[j+1],A[j]

    
def SelectionSort(A):
    loop = len(A)-1
    for i in range(loop):
        mini = i
        for j in range(i+1,loop+1):
            if A[j][1] < A[mini][1]:
                mini = j
        if i != mini:
            A[i],A[mini]=A[mini],A[i]            

    
N = int(input())
S = input().strip().split()
SS = S.copy()

BubbleSort(S)
for i in range(N):
    if i == N-1:
        print(S[i])
    else:
        print(S[i],end=' ')
print('Stable')

        
SelectionSort(SS)
for i in range(N):
    if i == N-1:
        print(SS[i])
    else:
        print(SS[i],end=' ')
if SS == S:
    print('Stable')
else:
    print('Not stable')


# Example run
# Input:
-163
cMzW>KkLJ
# Output:
Stable
Stable
n = int(input())
lst = input().split()
bub, sel = [lst]*2
sls = []
for i in range(n):
    m = i
    li = lst[i][0]
    if not li in sls:
        sls.append(li)
    for j in range(n-1,i,-1):
        if bub[j] < bub[j-1]:
            bub[j-1:j+1] = bub[j], bub[j-1]
    for k in range(i, n):
        if sel[k][1] < sel[k][1]:
            m = k
    if m != i:
        sel[i], sel[m] = sel[m], sel[i]

def stable(sort):
    s = 0
    for i in range(1,n):
        if sort[i][1] == sort[i-1][1] & sls.index(sort[i][0]) < sls.index(sort[i-1][0]):
            s += 1
    print('Not stable' if s else 'Stable')
    
print(*bub)
stable(bub)
print(*sel)
stable(sel)

# Example run
# Input:
-6325
4g#.Gc
# Output:
4g#.Gc
Stable
4g#.Gc
Stable
def bubble_sort(r, n):
    flag = True  # ??£??\????´?????????¨????????°
    while flag:
        flag = False
        for i in range(n - 1, 0, -1):
            if r[i - 1][1] > r[i][1]:
                r[i - 1], r[i] = r[i], r[i - 1]
                flag = True
    return r


def select_sort(r, n):
    for i in range(0, n):
        minj = i
        for j in range(i, n):
            if r[j][1] < r[minj][1]:
                minj = j
        if i != minj:
            r[i], r[minj] = r[minj], r[i]
    return r


def stable_sort(r, sort_r):
    for i in range(len(r)):
        for j in range(i + 1, len(r)):
            for a in range(len(sort_r)):
                for b in range(a + 1, len(sort_r)):
                    if r[i][1] == r[j][1] and r[i] == sort_r[b] and r[j] == sort_r[a]:
                         return "Not stable"

    return "Stable"


N = int(input())
R = list(input().split())
C = R[:]
BS_R = bubble_sort(R, N)
SS_R = select_sort(C, N)
print(*BS_R)
print(stable_sort(R, BS_R))
print(*SS_R)
print(stable_sort(R, SS_R))

# Example run
# Input:
-293149433
RH#y0
# Output:
RH#y0
Stable
RH#y0
Stable
def BSort(A,n):
    flag=1
    while flag:
        flag=0
        for i in range(n-1,0,-1):
            if A[i][1]<A[i-1][1]:
                A[i],A[i-1]=A[i-1],A[i]
                flag=1

def SSort(A,n):
    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]

n = int(input())

A = list(input().split())
B=A[:]

BSort(A,n)
print(' '.join(A))
print('Stable')
SSort(B,n)
print(' '.join(B))

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



# Example run
# Input:
-2530418
:$oOB?6
# Output:
:$oOB?6
Stable
:$oOB?6
Stable
#coding:utf-8
#1_2_C

def BubbleSort(cards, n):
    for i in range(n):
        for j in range(n-1, i, -1):
            if cards[j][1] < cards[j-1][1]:
                cards[j], cards[j-1] = cards[j-1], cards[j]
    return cards

def SelectionSort(cards, n):
    for i in range(n):
        print(cards)
        minj = i
        for j in range(i, n):
            if cards[minj][1] > cards[j][1]:
                minj = j
        cards[i], cards[minj] = cards[minj], cards[i]
    return cards

n = int(input())
cardsR = input().split()
cardsS = cardsR[:]

print(BubbleSort(cardsR, n))
print("Stable")
print(SelectionSort(cardsS, n))
print("Stable" if cardsR == cardsS else "Not stable")

# Example run
# Input:
-675765611
"O?Wixhv
# Output:
['"O?Wixhv']
Stable
['"O?Wixhv']
Stable
# -*- coding: utf-8 -*-


def bubble_sort(cards, num):
    for tail in range(num-1, 0, -1):
        for right in range(0, tail):
            left = right + 1
            if cards[left][1] < cards[right][1]:
                cards[right], cards[left] = cards[left], cards[right]

    print(list_to_str(cards))


def selection_sort(cards, num):
    for head in range(num):
        min_i = head

        for target in range(head+1, num):
            if cards[target][1] < cards[min_i][1]:
                min_i = target
        cards[head], cards[min_i] = cards[min_i], cards[head]

    print(list_to_str(cards))


def is_stable(before, after, num):
    for i in range(num):
        for j in range(i+1, num):
            for a in range(num):
                for b in range(a+1, num):
                    if before[i][1] == before[j][1]\
                    and before[i] == after[b]\
                    and before[j] == after[a]:
                        return 'Not stable'
    return 'Stable'


def list_to_str(l, delimiter=' '):
    # The default delimiter is one space.
    return delimiter.join([str(v) for v in l])


if __name__ == '__main__':
    num = int(input())
    cards = input().split()
    cards_for_bubble = cards.copy()
    cards_for_selection = cards.copy()

    bubble_sort(cards_for_bubble, num)
    print(is_stable(cards, cards_for_bubble, num))

    selection_sort(cards_for_selection, num)
    print(is_stable(cards, cards_for_selection, num))

# Example run
# Input:
-7339797
vbT
# Output:
vbT
Stable
vbT
Stable
def BubbleTrump(C, N):
    i = 0
    while i < N:
        j = N - 1
        while j > i:
            if int(C[j][1]) < int(C[j-1][1]):
                c = C[j]
                C[j] = C[j - 1]
                C[j - 1] = c
            j -= 1
        i += 1
    return C

def SelectionTrump(C, N):
    i = 0
    while i < N:
        minj = i
        j = i
        while j < N:
            if int(C[j][1]) < int(C[minj][1]):
                minj = j
            j += 1
        if minj != i:
            c = C[i]
            C[i] = C[minj]
            C[minj] = c
        i += 1
    return C

n = int(input())
C = list(map(str, input().split(' ')))
ans = ''
Cb = BubbleTrump(C.copy(), n)
ans += ' '.join(map(str, Cb)) + '\nStable\n'
Cs = SelectionTrump(C.copy(), n)
q = 0
f = 1
while q < n:
    if Cb[q] != Cs[q]:
        f = 0
    q += 1
ans += ' '.join(map(str, Cs)) + '\n'
if f == 0:
    ans += 'Not stable'
else:
    ans += 'Stable'
print(ans)


# Example run
# Input:
-22
LAkU
# Output:
LAkU
Stable
LAkU
Stable
from typing import List, NamedTuple


class Card(NamedTuple):
    suit: str
    value: int


def bubble_sort(cards: List[Card]):
    for i in range(len(cards)):
        for j in range(len(cards) - 1, i, -1):
            if cards[j].value < cards[j - 1].value:
                cards[j], cards[j - 1] = cards[j - 1], cards[j]


def selection_sort(cards: List[Card]):
    for i in range(len(cards)):
        minj = i
        for j in range(i, len(cards)):
            if cards[j].value < cards[minj].value:
                minj = j
        cards[i], cards[minj] = cards[minj], cards[i]


def gen_numbet_card_pair(cards: List[Card]):
    return {n: [c for c in cards if c.value == n] for n in range(1, 10)}


def is_stable(in_cards: List[Card], out_cards: List[Card]):
    in_lists = gen_numbet_card_pair(in_cards)
    out_lists = gen_numbet_card_pair(out_cards)
    for n in range(10):
        if in_lists.get(n, []) != out_lists.get(n, []):
            return False
    return True


def printing(arr, f):
    b_arr = arr.copy()
    f(b_arr)
    print(" ".join([c.suit+str(c.value) for c in b_arr]))
    print("Stable" if is_stable(arr, b_arr) else "Not stable")


n = int(input())
cards: List[Card] = [Card(suit=x[0], value=int(x[1])) for x in input().split(" ")]
printing(cards, bubble_sort)
printing(cards, selection_sort)



# Example run
# Input:
26131
1748
# Output:
17
Stable
17
Stable
def bubbleSort(A,N):
    flag = 1
    sortedIndex = 0
    i = 0
    while flag == 1:
        flag = 0
        for j in range(N-1,sortedIndex,-1):
            if int(A[j][1]) < int(A[j-1][1]):
                v = A[j]
                A[j] = A[j-1]
                A[j-1] = v
                flag = 1
                i += 1

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

def isStable(before,after,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 before[i][1] == before[j][1] and before[i] == after[b] and before[j] == after[a]:
                        #print("i={} j={} a={} b={}".format(i,j,a,b))
                        return False
    return True

def bubble_is_stable(A,N):
    bubble = A.copy()
    bubbleSort(bubble,N)
    bubble_is_stable = isStable(A,bubble,N)
    bubblestr = ''
    for i in range(N):
        bubblestr += "{} ".format(bubble[i])
    print(bubblestr[:len(bubblestr)-1])
    if bubble_is_stable:
        print('Stable')
    else:
        print('Not stable')

def selection_is_stable(A,N):
    selection = A.copy()
    selectionSort(selection,N)
    selection_is_stable = isStable(A,selection,N)
    selectionstr = ''
    for i in range(N):
        selectionstr += "{} ".format(selection[i])
    print(selectionstr[:len(selectionstr)-1])
    if selection_is_stable:
        print('Stable')
    else:
        print('Not stable')

if __name__ == '__main__':
    N = int(input())
    A = [ _ for _ in input().split()]
    bubble_is_stable(A,N)
    selection_is_stable(A,N)



# Example run
# Input:
-1
c&j
# Output:

Stable

Stable
import copy
N = int(input())
A = input().split()
B = copy.copy(A)
boo = 1
while boo:
    boo = 0
    for i in range(N-1):
        if A[i][1] > A[i+1][1]:
            A[i], A[i+1] = A[i+1], A[i]
            boo = 1
print(*A)
print("Stable")
for i in range(N):
    mi = i
    for j in range(i,N):
        if B[mi][1] > B[j][1]:
            mi = j
    B[i], B[mi] = B[mi], B[i]
    print(B)
if A==B:
    print(*B)
    print("Stable")
else:
    print(*B)
    print("Not stable")



# Example run
# Input:
-86077887
i[%sQ
# Output:
i[%sQ
Stable
i[%sQ
Stable
'''
5
H4 C9 S4 D2 C3
'''
N = int(input())
C1 = list(map(str, input().split()))
C2 = [None] * N

for i in range(N):
  C2[i] = C1[i]

def bubble(C, N):
  #count = 0
  for i in range(0, N-1, 1):
    for j in range(N-1, i, -1):
      #print("j:{} C[j-1]:{} C[j]:{}".format(j, C[j-1], C[j]))
      if (int(C[j-1][1]) > int(C[j][1])):
        C[j-1], C[j] = C[j], C[j-1]
        #count += 1
        #print("Swapped. C:{}".format(C))

  print(str(C).replace('[', '').replace(']', '').replace(',', '').replace('\'', ''))
  print("Stable") # because buddle sort is stable sort

def selection(C, N):
  for i in range(N):
    minj = i
    for j in range(i+1, N):
      if (int(C[minj][1]) > int(C[j][1])):
        minj = j
    C[minj], C[i] = C[i], C[minj]

  print(str(C).replace('[', '').replace(']', '').replace(',', '').replace('\'', ''))

def main():
  bubble(C1, N)
  selection(C2, N)

  if (C1 == C2):
    print("Stable")
  else:
    print("Not stable")

main()



# Example run
# Input:
-11989124
=C>#:pjLk
# Output:
=C>#:pjLk
Stable

Not stable
# -*- coding: utf-8 -*-

class Card:
    def __init__(self, str):
        self.suit  = str[0]
        self.value = int(str[1])

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

def swap(A, i, j):
    tmp  = A[i]
    A[i] = A[j]
    A[j] = tmp

def BubbleSort(C, N):
    for i in range(N):
        for j in range(N-1, i, -1):
            if C[j].value < C[j-1].value:
                swap(C, j, j-1)  # C[j] と C[j-1] を交換

def SelectionSort(C, N):
    for i in range(N):
        minj = i
        for j in range(i, N):
            if C[j].value < C[minj].value:
                minj = j
        swap(C, i, minj)  # C[i] と C[minj] を交換

def isStable(A, B):
    for i in range(1, len(B)):
        if B[i-1].value == B[i].value:
            for j in range(len(A)):
                if A[j] == B[i-1]: break
                if A[j] == B[i]:   return False
    return True

N = int(input())
A = [Card(t) for t in input().split()]
if len(A) != N: raise

B = A[:]
S = A[:]
BubbleSort(B, N)
SelectionSort(S, N)
print(' '.join(map(str, B)))
print('Stable' if isStable(A, B) else 'Not stable')
print(' '.join(map(str, S)))
print('Stable' if isStable(A, S) else 'Not stable')


# Example run
# Input:
1
-3108573
# Output:
-3
Stable
-3
Stable
import copy
def BubbleSort(d,N):
    for i in range(0,N):
        for j in range(i+1,N)[::-1]:#
            if d[j][1] < d[j-1][1]:
                t=d[j]
                d[j]=d[j-1]
                d[j-1]=t 
    return d

def selectionSort(d,N):
    c1 = 0
    for i in range(0,N):
        minj = i    #カーソル
        for j in range(i,N):
            if d[j][1] < d[minj][1]:
                minj = j
        if(i!=minj):
            t = d[i]
            d[i] = d[minj]
            d[minj] = t
            c1+=1     
    return d           

if __name__=="__main__":
    n = int(input())
    l = [i for i in input().split()]
    l2=copy.deepcopy(l)
    print(' '.join(BubbleSort(l,n)))#pythonの場合は一回関数入れるとlは更新されてしまうのでlをコピーかなんかでもう一個作っとく必要がある
    print('Stable')#バブルソートは同じ数の順番入れ替わらないんすよね
    print(' '.join(selectionSort(l2,n)))
    if l != l2:
        print('Not stable')
    else:
        print('Stable')


# Example run
# Input:
-1
hd](
# Output:
hd](
Stable
hd](
Stable
N = int(input())
card_list_source = input().split(' ')

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

def SelectionSort(card_list, N):
    for i in range(N):
        min_index = i
        for j in range(i+1, N):
            if int(card_list[j][1]) < int(card_list[min_index][1]):
                min_index = j
        if min_index != i:
            temp = card_list[i]
            card_list[i] = card_list[min_index]
            card_list[min_index] = temp
    return card_list

def isStable(card_list_A, card_list_B):
    N = len(card_list_A)
    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 int(card_list_A[i][1]) == int(card_list_A[j][1]) and card_list_A[i] == card_list_B[b] and card_list_A[j] == card_list_B[a]:
                        return 'Not stable'
    return 'Stable'

def make_out_str(card_list):
    out_str = ''
    for i, card in enumerate(card_list):
        out_str += card
        if i < len(card_list) - 1:
            out_str += ' '
    return out_str

card_list_bubble = BubbleSort(card_list_source.copy(), N)
print(make_out_str(card_list_bubble))
print(isStable(card_list_bubble, card_list_source))

card_list_selection = SelectionSort(card_list_source.copy(), N)
print(make_out_str(card_list_selection))
print(isStable(card_list_selection, card_list_source))





# Example run
# Input:
-331
P$0[(XQ6o
# Output:
P$0[(XQ6o
Stable
P$0[(XQ6o
Stable
N=int(input())
L=input().split( )
#リストがmutableなので以下ではコピーできていない
#B=L
#S=L
B=L[:]
S=L[:]
for i in range(N):
    j=N-1
    while j>i:
        if B[j][1]<B[j-1][1]:
            temp =B[j]
            B[j]=B[j-1]
            B[j-1]=temp

        j-=1

for i in range(N):
    minj= i
    j=i
    while j<N:
        if S[j][1]<S[minj][1]:
            minj=j
            j+=1
            #print(S[minj])
        else:j+=1

#j+=1してねぇｗ
#if終了後に交換なので以下のインデントはifと同列
#じゃなくてifより上でwhileと同列
#jでなくてi
#この辺散々間違えたが、間違えた時の挙動が追いきれない
    temp =S[i]
    S[i]=S[minj]
    S[minj]=temp
    #print(S,i,minj)

for i in range(N):
    if i!=N-1:
        print(f"{B[i]}",end=" ")
    else:
        print(f"{B[i]}")
print("Stable")

for i in range(N):
    if i!=N-1:
        print(f"{S[i]}",end=" ")
    else:
        print(f"{S[i]}")
flag=1
for i in range(N):
    if B[i]!=S[i]:
        flag=0
if flag==1:
    print("Stable")
if flag==0:
    print("Not stable")



# Example run
# Input:
-5654
5A|aI
# Output:
Stable
Stable