Felix6326727/beyond-accuracy-code-comprehension huggingface dataset:
# -*- coding: utf-8 -*-
"""
B - Palindrome-phobia
https://atcoder.jp/contests/cf17-final/tasks/cf17_final_b

"""
import sys


from collections import Counter

def solve(S):
    cnt = Counter(S)
    res = sorted([[v, k] for k, v in cnt.items()], reverse=True)

    ch = res[0][1]
    prev = None
    cnt[ch] -= 1
    if cnt[ch] == 0:
        del cnt[ch]

    d = {'ab': 'c', 'ac': 'b', 'ba': 'c', 'bc': 'a', 'ca': 'b', 'cb': 'a'}

    while cnt:
        if prev is None:
            if len(res) < 2:
                return 'NO'
            else:
                prev = ch
                ch = res[1][1]
                cnt[ch] -= 1
                if cnt[ch] == 0:
                    del cnt[ch]
        else:
            n_ch = d[prev+ch]
            if cnt[n_ch] > 0:
                prev, ch = ch, n_ch
                cnt[n_ch] -= 1
                if cnt[n_ch] == 0:
                    del cnt[n_ch]
            else:
                return 'NO'
    return 'YES'


def main(args):
    S = input()
    ans = solve(S)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])


# Example run
# Input:
55
# Output:
NO
S = input()
na = S.count("a")
nb = S.count("b")
nc = S.count("c")
n1, n2, n3 = sorted([na, nb, nc])
if n3 <= n1+1:
  print("YES")
else:
  print("NO")


# Example run
# Input:
|@`(
# Output:
YES
s=input()
t = set(s)
if len(t) != 3:
    print("NO")
else:
    a = s.count("a")
    b = s.count("b")
    c = s.count("c")
    M = max(a,b,c)
    m = min(a,b,c)
    if M - m >1 :
        print("NO")
    else:
        print("YES")



# Example run
# Input:
.P&aOD
# Output:
NO
from collections import defaultdict

S = input()
d = defaultdict(int)

for i in range(len(S)):
  d[S[i]] += 1

ma = max(d["a"], d["b"], d["c"])
mi = min(d["a"], d["b"], d["c"])

if ma-mi > 1:
  print("NO")
else:
  print("YES")

# Example run
# Input:
09{=
# Output:
YES
from collections import Counter as c
s=input()
d=c(s)

ca,cb,cc=d["a"],d["b"],d["c"]
if abs(ca-cb)<=1 and abs(ca-cc)<=1 and abs(cb-cc)<=1:
  print("YES")
else:
  print("NO")


# Example run
# Input:
!&\D5sO
# Output:
YES
s=list(input())
a=0
b=0
c=0
for i in range(len(s)):
    if s[i]=='a':
        a+=1
    elif s[i]=='b':
        b+=1
    else:
        c+=1
if(a<(int(len(s)/3)) or b<(int(len(s)/3)) or c<(int(len(s)/3))):
    print('NO')
else:
    if len(s)%3!=2:
        print('YES')
    else:
        if max(a,b,c)==(int(len(s)/3)+2):
            print('NO')
        else:
            print('YES')


# Example run
# Input:
3132478
# Output:
NO
from collections import Counter
s = list(input())

count = Counter(s)
if len(s) <= 3:
  if len(s) == 1: print("YES")
  elif len(count.keys()) == len(s): print("YES")
  else: print("NO")
else:
  if len(count.keys()) <= 2: print("NO")
  elif max(count.values()) - min(count.values()) <= 1: print("YES")
  else: print("NO")


# Example run
# Input:
0.005820226422590676
# Output:
NO
import collections
s = list(input())
s = collections.Counter(s)
a = s["a"]
b = s["b"]
c = s["c"]

if max(a,b,c) - min(a,b,c) <= 1:
  print("YES")
else:
  print("NO")

# Example run
# Input:
rZz}
# Output:
YES
s = input()
a = s.count('a')
b = s.count('b')
c = s.count('c')
a, b, c = sorted([a, b, c])
if a==b==c:
    print('YES')
elif a==b and c-b < 2:
    print('YES')
elif b-a < 2 and b==c:
    print('YES')
else:
    print('NO')

# Example run
# Input:
},,Y
# Output:
YES
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

# Summarize count of factor within list
def summarize_list(l):
  sl=sorted(l)

  a=sl[0]
  c=1
  res=[]

  for x in sl[1:]:
    if x==a:
      c+=1
    else:
      res.append([a,c])
      a=x
      c=1
  res.append([a,c])

  return res

def main():
  s=list(S())
  t=summarize_list(s)

  if len(s)==1:
    return 'YES'
  if len(s)==2:
    if len(t)==2:
      return 'YES'
    return 'NO'
  if len(t)==2:
    return 'NO'

  t=sorted(t,key=lambda x:x[1])
  # print(t)
  if t[2][1]-t[0][1]>=2:
    return 'NO'
  return 'YES'

# main()
print(main())


# Example run
# Input:
1.1080147773648895e-103
# Output:
YES
S = input()

dic = {}

for s in S:
    dic[s] = dic.get(s, 0) + 1

L = dic.values()
sum_L = sum(L)
max_n = max(L)
min_n = min(L)

if (sum_L - max_n) // 2 == min_n:
    if max_n == min_n:
        print('NO')
    else:
        print('YES')
elif max_n == 1 and sum_L == 1:
    print('YES')
else:
    print('NO')


# Example run
# Input:
ANQH]
# Output:
NO
s=input()
cnta=0
cntb=0
cntc=0
for i in range(len(s)):
  if s[i]=='a':
    cnta+=1
  elif s[i]=='b':
    cntb+=1
  else:
    cntc+=1
if len(s)%3==0:
  if cnta==cntb==cntc:
    print('YES')
  else:
    print('NO')
else:
  if max(cnta,cntb,cntc)==min(cnta,cntb,cntc)+1:
    print('YES')
  else:
    print('NO')

# Example run
# Input:
-+%Exq\|
# Output:
NO
# -*- coding: utf-8 -*-
from collections import Counter

def pri(x):
    if x == 1:
        return print("Yes")
    else:
        return print("No")

S = list(input())

S.sort()
c = list(Counter(S).values())
if len(c) <= 2:
    for _ in range(3-len(c)):
        c.append(0)
c.sort(reverse = True)

if c[0] >= c[1] - 1:
    if c[2] >= c[0] - 1:
        pri(1)
    else:
        pri(0)
else:
    pri(0)

# Example run
# Input:
1
# Output:
Yes
from collections import Counter
s = sorted(list(Counter(list(input())).values()))[::-1]
a = s[0]
for i in s:
  if a==i or a==i+1:
    continue
  else:
    print('NO')
else:
  print("YES")

# Example run
# Input:
-4.152476289597669e-92
# Output:
NO
NO
NO
NO
NO
NO
NO
NO
YES
#!/usr/bin/env python3
import collections
import itertools as it
import math
#import numpy as np
 
s  = input()
#  = int(input())
#  = map(int, input().split())
#  = list(map(int, input().split()))
#  = [int(input()) for i in range(N)]
#
c = collections.Counter(s)

v = [v_ for v_ in c.values() if v_ != 0]

if len(s) == 1:
    print('YES')
    exit()

if len(s) == 2: 
    print('YES' if len(v) == 2 else 'NO')
    exit()

if len(v) <= 2:
    print('NO')
else:
    print('YES' if max(v) - min(v) <= 1 else 'NO')


# Example run
# Input:
G9$uz\!r(
# Output:
YES
x=list(map(input().count,"abc"));print("YNEOS"[max([abs(x[i]-x[~-i%3])for i in[0]*3])>1::2])

# Example run
# Input:
Y)lx&:Sr
# Output:
YES
from collections import Counter
c = Counter(input())
labels = ['a', 'b', 'c']
min_cnt = min(c[label] for label in labels)
cnt = [c[label] - min_cnt for label in labels]
for x in cnt:
    if x in (0, 1):
        continue
    print('NO')
    break
else:
    print('YES')


# Example run
# Input:
t84
# Output:
YES
s=str(input())
ans=0
if len(s)==1:
  print("NO")
else:
  for i in range(1,len(s)-2):
    if s[i]==s[i+1]:
      ans+=1
      break
    elif s[i]==s[i+2]:
      ans+=1
      break
    else:
      ans+=0   

  if s[-2]==s[-1]:
    ans+=1
  
  if ans==0:
    print("YES")
  else:
    print("NO")
    
  
  



# Example run
# Input:
3.83835494570401e-85
# Output:
NO
s=input()
t = set(s)
if len(t) != 3:
    if len(t)==1:
        print("YES")
    else:
        print("NO")
else:
    a = s.count("a")
    b = s.count("b")
    c = s.count("c")
    M = max(a,b,c)
    m = min(a,b,c)
    if M - m >1 :
        print("NO")
    else:
        print("YES")


# Example run
# Input:
:q|Hq
# Output:
NO
#同じ文字の間隔を2文字以上空ける　abcabcabc,,,,,
s=input()
if len(s)==1:
    print("YES")
    exit()
    
c=[0,0,0]
for i in range(len(s)):
    if s[i]=="a":
        c[0]+=1
    elif s[i]=="b":
        c[1]+=1
    elif s[i]=="c":
        c[2]+=1
if max(c)-min(c)>=2:
    print("NO")
else:
    print("YES")

# Example run
# Input:
$h8zRH#
# Output:
YES
def count(l):
    res = {'a':0, 'b':0, 'c':0}
    for d in l:
        if d in res:
            res[d] += 1
        else:
            res[d] = 1
    return res

string = input()
cnt = count(string).values()
if max(cnt) - min(cnt) < 2:
    print('YES')
else:
    print('NO')



# Example run
# Input:
1.3675062472339184e-89
# Output:
NO
a=int(input())
v=int(input())
b=int(input())
w=int(input())
t=int(input())
x = (t * v) + a;
y = (t* w) + b;

if((x-y)>=0):
    print("YES")
else:
    print("NO")

# Example run
# Input:
-89451
-131587518
-3766
9062461
72046879
# Output:
NO
import random

S = str(input())

A = list(S)

N = random.sample(A, k=3)

print(N[0]+N[1]+N[2])

# Example run
# Input:
19?2
# Output:
?92
a = int(input())
v = int(input())
b = int(input())
w = int(input())
t = int(input())
x = 0
flag = False

while x <= t:
    if a < b:
        a += v
        b += w
    elif a > b:
        a -= v
        b -= w
    else:
        flag = True
        break
else:
    if a == b:
        flag = True

if flag:
    print("YES")
else:
    print("NO")


# Example run
# Input:
1
452230665
1
1547
-15
# Output:
YES
A = int(input())
V = int(input())
B = int(input())
W = int(input())
T = int(input())

if (B-A)/(W-V) <= T:
    print('YES')
else:
    print('NO')

# Example run
# Input:
-1
-106
1214970
54504816
-1005173
# Output:
NO
#鬼
A=int(input())
V=int(input())
#逃げ
B=int(input())
W=int(input())
#逃げる時間
T=int(input())

for k in range(1, T+1):
    a=A+(V*k)
    b=B+(W*k)
    if (a == b):
        print('YES')
    else:
        print('NO')

# Example run
# Input:
-61
-196
-418682
6673
113
# Output:
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
a = int(input())
v = int(input())
b = int(input())
w = int(input())
t = int(input())

move_a = v * t + a
move_b = w * t + b

if move_a > move_b:
    print("YES")
else:
    print("NO")

# Example run
# Input:
-516
148298
-1643990
363865392
-1377730
# Output:
YES
a=int(input())
v=int(input())
b=int(input())
w=int(input())
t=int(input())
x = (t * v) + a;
y = (t* w) + b;


if((x-y)>0):
    print("YES")
else:
    print("NO")

# Example run
# Input:
-10537
-3072224
-29
11835
0
# Output:
NO
n = list(map(int,input().split()))
m = list(map(int,input().split()))
k = int(input())

if n[0] >= m[0]:
    print("NO")

for x in range(k):
    if n[0] + n[1]*(x+1) >= m[0] + m[1]*(x+1):
        print("YES")
        exit()

print("NO")

# Example run
# Input:
-7031780
415326
-1201474778
# Output:
NO
a=int(input())
v=int(input())
b=int(input())
w=int(input())
t=int(input())
x = (t * v) + a;
y = (t* w) + b;


if((x-y)>=0):
    print("YES")
else:
    print("NO")

# Example run
# Input:
0
-57243
1744224
-7142130
14747
# Output:
YES
a_v = list(map(int, input().split()))
b_w= list(map(int, input().split()))

t = int(input())

a = a_v[0]
b = b_w[0]
for _ in range(t):
    a += a_v[1]
    b += b_w[1]
if a >= b:
    print("YES")
else:
    print("NO")

# Example run
# Input:
-52564348
-7737
-126905272
# Output:
NO
a = int(input())
v = int(input())
b = int(input())
w = int(input())
t = int(input())
d = v * t
e = w * t
if a + d >= b + e:
    print("YES")
else:
    print("NO")

# Example run
# Input:
449660
0
-83
-39355
1
# Output:
YES
a = int(input())
v = int(input())
b = int(input())
w = int(input())
t = int(input())
a += t * v;
b += t * w;
if (a < b):
  print("NO")
else:
  print("YES")


# Example run
# Input:
-4144845
-5036400
969556
540
-46896159
# Output:
YES
l=[]
r=[]
l.append(int(input()))
while l:
    o=int(input())
    if not o:
        r.append(l.pop())
    else:
        l.append(o)
for i in r:
    print(i)



# Example run
# Input:
21
0
# Output:
21
s=[int(input())]
while(len(s)!=0):
    n=int(input())
    if n==0:
        print(s.pop())
    else:
        s.append(n)

# Example run
# Input:
-970702
0
# Output:
-970702
li = []
li.append(int(input()))
depth = 1
while depth > 0:
    x = int(input())
    if x == 0:
        print(li.pop())
        depth -= 1
    else:
        li.append(x)
        depth += 1

# Example run
# Input:
1
0
# Output:
1
l=[]
l.append(int(input()))
while l:
    o=int(input())
    if not o:
        print(l.pop())
    else:
        l.append(o)



# Example run
# Input:
35
0
# Output:
35
# Switching Railroad Cars
from collections import deque
num = int(input())
stk = deque()
while 1:
    if num == 0:
        print(stk.pop())
    else:
        stk.append(num)
    try: num = int(input())
    except EOFError: break
while stk: print(stk.pop())


# Example run
# Input:
743812855
# Output:
743812855
stack = []
stack.append(int(input()))
while stack:
    inp = int(input())
    if inp == 0:
        a = stack[-1]
        del stack[-1]
        print(a)
    else:
        stack.append(inp)

# Example run
# Input:
-3439167
0
# Output:
-3439167
stack = []
stack.append(int(input()))
ans= []
while stack:
    inp = int(input())
    if inp == 0:
        a = stack[-1]
        del stack[-1]
        ans.append(a)
    else:
        stack.append(inp)
print(*ans, sep="\n")

# Example run
# Input:
23038
0
# Output:
23038
li = []
li.append(int(input()))
depth = 1
while depth > 0:
    x = int(input())
    if x == 0:
        print(li.pop())
        depth -= 1
    else:
        li.append(x)
        depth += 1

# Example run
# Input:
3376
0
# Output:
3376
l=[]
l.append(int(input()))
while l:
    o=int(input())
    if not o:
        print(l.pop())
    else:
        l.append(o)



# Example run
# Input:
446
0
# Output:
446
x = int(input())

ans = x // 11 * 2
print(ans + (x % 11 > 0) + (x % 11 > 6))


# Example run
# Input:
152
# Output:
28
def is_prime(N):
    if N < 2:
        return False
    i = 2
    while i*i <= N:
        if N % i == 0:
            return False
        i += 1
    return True


def main():
    N = int(input())
    if not is_prime(N):
        dsum = 0
        for c in str(N):
            dsum += int(c)
        if N == 1 or N % 10 in [2, 4, 5, 6, 8, 0] or dsum % 3 == 0:
            print("Not Prime")
            return
    print("Prime")


if __name__ == "__main__":
    main()


# Example run
# Input:
1
# Output:
Not Prime
import copy

def show(C):
    for i in range(len(C)):
        if i :
            print(' ', end = '')
        print(C[i], end = '')
    print()

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]
    show(C)

def SelectionSort(D, N):
    for i in range(N):
        min_j = i
        for j in range(i, N):
            if D[j][1] < D[min_j][1]:
                min_j = j
        D[i], D[min_j] = D[min_j], D[i]
    show(D)

N = int(input())
C = [i for i in input().split()]
D = copy.copy(C)

bubbleSort(C, N)
print('Stable')
SelectionSort(D, N)
if C == D:
    print('Stable')
else:
    print('Not stable')



# Example run
# Input:
-146574716
RH#y0
# Output:
RH#y0
Stable
RH#y0
Stable
def show (nums):
    for i in range(len(nums)):
        if i!=len(nums)-1:
            print(nums[i],end=' ')
        else :
            print(nums[i])

def bubble(A):
    flag = True
    i = 0
    n = len(A)
    while(flag):
        flag = False
        for j in range(i+1,n)[::-1]:
            if A[j][1] < A[j-1][1]:
                A[j],A[j-1] = A[j-1],A[j]
                flag = True
        i += 1

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

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

bubble(A)
selection(B)

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




# Example run
# Input:
-1
Rn\\a&K
# Output:
Rn\\a&K
Stable
Rn\\a&K
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')

    cards.show()

if __name__ == '__main__':
    run()


# Example run
# Input:
-8
-39
# Output:
-39
Stable
-39
Stable
-39
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]
if A==B:
    print(*B)
    print("Stable")
else:
    print(*B)
    print("Not stable")



# Example run
# Input:
-4816
:i8gz
# Output:
:i8gz
Stable
:i8gz
Stable
def bubbleSort(cards):
    n = len(cards)
    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 = len(cards)
    for i in range(n):
        minj = i
        for j in range(i, n):
            if cards[j][1] < cards[minj][1]:
                minj = j
        cards[i], cards[minj] = cards[minj], cards[i]
    
    return cards


def isStableSort(initialArray, resultArray):
    n = len(initialArray)
    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 initialArray[i][1] == initialArray[j][1]:
                        if initialArray[i] == resultArray[b]:
                            if initialArray[j] == resultArray[a]:
                                return False
    
    return True


n = int(input())
array = [x for x in input().split()]
cards = [[a[0], a[1]] for a in array]
cardsForBubble = cards[:]
cardsForSelection = cards[:]

bSort = bubbleSort(cardsForBubble)
sSort = selectionSort(cardsForSelection)

resultForBubble = []
resultForSelection = []

for b in bSort:
    resultForBubble.append(''.join(b))
for s in sSort:
    resultForSelection.append(''.join(s))

print(*resultForBubble)
if isStableSort(array, resultForBubble):
    print("Stable")
else:
    print("Not stable")

print(*resultForSelection)
if isStableSort(array, resultForSelection):
    print("Stable")
else:
    print("Not stable")


# Example run
# Input:
28
G)(MW
# Output:
G)
Stable
G)
Stable
def compare_cards(a, b):
    return a[1] < b[1]

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

def selection_sort(A):
    for i in range(len(A)):
        mini = i
        for j in range(i, len(A)):
            if compare_cards(A[j], A[mini]):
                mini = j
        A[i], A[mini] = A[mini], A[i]

def check_stable(originA, sortedA):
    for i in range(len(originA)-1):
        if not compare_cards(sortedA[i], sortedA[i+1]):
            if originA.index(sortedA[i]) > originA.index(sortedA[i+1]):
                return "Not stable"
    return "Stable"

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

bubbleA = list(A)
selectionA = list(A)

bubble_sort(bubbleA)
selection_sort(selectionA)

print(*bubbleA)
print(check_stable(A, bubbleA))

print(*selectionA)
print(check_stable(A, selectionA))

# Example run
# Input:
441722
^>x#
# Output:
^>x#
Stable
^>x#
Stable
n = int(input())
cards = list(input().split())
cards1 = cards.copy()
# cnt = 0
# for i in range(n):
#     minj = i
#     for j in range(i,n):
#         if int(cards[minj][1]) > int(cards[j][1]):
#             minj = j
#     if i != minj:
#         cnt += 1
#     cards[i], cards[minj] = cards[minj], cards[i]
#     print(cards)

#['D2', 'C3', 'S4', 'H4', 'C9']




def BubbleSort(cards):

    for i in range(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 SelectionSort(cards):
    cnt = 0
    for i in range(n):
        minj = i
        for j in range(i,n):
            if int(cards[minj][1]) > int(cards[j][1]):
                minj = j
        if i != minj:
            cnt += 1
        cards[i], cards[minj] = cards[minj], cards[i]

    return cards

a = BubbleSort(cards)
b = SelectionSort(cards1)

print(*a)
print("Stable")
print(*b)
if a == b:
    print("Stable")
else:
    print("Not stable")







# Example run
# Input:
-185
L(?J7Ozo
# Output:
L(?J7Ozo
Stable
L(?J7Ozo
Stable
n = int(input())
a = list(input().split())
b = a[:]
s = "Stable"
c, d = [[] for i in range(9)], [[] for i in range(9)]
for i in range(n):
    c[int(a[i][1])-1].append(a[i][0])
for _ in range(n):
    for i in range(n-1,0,-1):
        if int(b[i][1]) < int(b[i-1][1]):
            b[i], b[i-1] = b[i-1], b[i]
print(" ".join(map(str,b)))
print(s)
for i in range(n):
    min = a[n-1]
    ch = n - 1
    for j in range(n-2,i-1,-1):
        if int(a[j][1]) <= int(min[1]):
            min = a[j]
            ch = j
    a[i], a[ch] = a[ch], a[i]
for i in range(n):
    d[int(a[i][1])-1].append(a[i][0])
if c != d:
    s = "Not stable"
print(" ".join(map(str,a)))
print(s)


# Example run
# Input:
-1
L]]x-M
# Output:
L]]x-M
Stable
L]]x-M
Stable
from copy import deepcopy
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]

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]

N = int(input())
C = list(map(str, input().split()))
C1 = deepcopy(C)
C2 = deepcopy(C)
bubbleSort(C1, N)
selectionSort(C2, N)
O = [[] for _ in range(9)]
for i in range(N):
    j = int(C[i][1]) - 1
    O[j].append(C[i][0])
O1 = [[] for _ in range(9)]
for i in range(N):
    j = int(C1[i][1]) - 1
    O1[j].append(C1[i][0])
O2 = [[] for _ in range(9)]
for i in range(N):
    j = int(C2[i][1]) - 1
    O2[j].append(C2[i][0])
for i in range(N):
    if i == N - 1:
        print(C1[i])
    else:
        print(C1[i], end=' ')
if O == O1:
    print('Stable')
else:
    print('Not stable')
for i in range(N):
    if i == N - 1:
        print(C2[i])
    else:
        print(C2[i], end=' ')
if O == O2:
    print('Stable')
else:
    print('Not stable')


# Example run
# Input:
-1836
@53vp2<ju
# Output:
Stable
Stable