import copy

n = int(raw_input())
cards = raw_input().split()
cards1 = copy.deepcopy(cards)
cards2 = copy.deepcopy(cards)

def isbig(card1, card2):
	if int(card1[1]) > int(card2[1]):
		return 2
	elif int(card1[1]) == int(card2[1]):
		return 1
	else:
		return 0

def BubbleSort(c, n):
	temp = 0
	for i in range(n):
		for j in reversed(range(i+1,n)):
			if isbig(c[j], c[j-1]) == 0:
				temp = c[j]
				c[j] = c[j-1]
				c[j-1] = temp
	return c

def SelectionSort(c, n):
	temp = 0
	for i in range(n):
		minj = i
		for j in range(i,n):
			if isbig(c[j], c[minj]) == 0:
				minj = j
		temp = c[i]
		c[i] = c[minj]
		c[minj] = temp
		#print("*{:}".format(c))
	return c

def isstable(unsort, sort):
	for i in range(n):
		for j in range(i+1,n):
			for k in range(n):
				for l in range(k+1,n):
					if isbig(unsort[i], unsort[j]) == 1 and unsort[i] == sort[l] and unsort[j] == sort[k]:
						return 0
	return 1

for i in range(n):
	if i != n-1:
		print BubbleSort(cards1, n)[i],
	else:
		print BubbleSort(cards1, n)[i]

if isstable(cards, BubbleSort(cards1, n)) == 1:
	print("Stable")
else:
	print("Not stable")

for i in range(n):
	if i != n-1:
		print SelectionSort(cards2, n)[i],
	else:
		print SelectionSort(cards2, n)[i]

if isstable(cards, SelectionSort(cards2, n)) == 1:
	print("Stable")
else:
	print("Not stable") import copy copy n = int(raw_input()) n int(raw_input()) int raw_input() raw_input cards = raw_input().split() cards raw_input().split() ().split () raw_input split cards1 = copy.deepcopy(cards) cards1 copy.deepcopy(cards) copy.deepcopy copy deepcopy cards cards2 = copy.deepcopy(cards) cards2 copy.deepcopy(cards) copy.deepcopy copy deepcopy cards def isbig(card1, card2):
	if int(card1[1]) > int(card2[1]):
		return 2
	elif int(card1[1]) == int(card2[1]):
		return 1
	else:
		return 0 isbig if int(card1[1]) > int(card2[1]):
		return 2
	elif int(card1[1]) == int(card2[1]):
		return 1
	else:
		return 0 int(card1[1]) > int(card2[1]) int(card1[1]) int card1[1] card1 1 int(card2[1]) int card2[1] card2 1 return 2 2 elif int(card1[1]) == int(card2[1]):
		return 1
	 int(card1[1]) == int(card2[1]) int(card1[1]) int card1[1] card1 1 int(card2[1]) int card2[1] card2 1 return 1 1 return 0 0 card1 card1 card2 card2 def BubbleSort(c, n):
	temp = 0
	for i in range(n):
		for j in reversed(range(i+1,n)):
			if isbig(c[j], c[j-1]) == 0:
				temp = c[j]
				c[j] = c[j-1]
				c[j-1] = temp
	return c BubbleSort temp = 0 temp 0 for i in range(n):
		for j in reversed(range(i+1,n)):
			if isbig(c[j], c[j-1]) == 0:
				temp = c[j]
				c[j] = c[j-1]
				c[j-1] = temp
	 i range(n) range n for j in reversed(range(i+1,n)):
			if isbig(c[j], c[j-1]) == 0:
				temp = c[j]
				c[j] = c[j-1]
				c[j-1] = temp
	 j reversed(range(i+1,n)) reversed range(i+1,n) range i+1 i 1 n if isbig(c[j], c[j-1]) == 0:
				temp = c[j]
				c[j] = c[j-1]
				c[j-1] = temp
	 isbig(c[j], c[j-1]) == 0 isbig(c[j], c[j-1]) isbig c[j] c j c[j-1] c j-1 j 1 0 temp = c[j] temp c[j] c j c[j] = c[j-1] c[j] c j c[j-1] c j-1 j 1 c[j-1] = temp c[j-1] c j-1 j 1 temp return c c c c n n def SelectionSort(c, n):
	temp = 0
	for i in range(n):
		minj = i
		for j in range(i,n):
			if isbig(c[j], c[minj]) == 0:
				minj = j
		temp = c[i]
		c[i] = c[minj]
		c[minj] = temp
		#print("*{:}".format(c))
	return c SelectionSort temp = 0 temp 0 for i in range(n):
		minj = i
		for j in range(i,n):
			if isbig(c[j], c[minj]) == 0:
				minj = j
		temp = c[i]
		c[i] = c[minj]
		c[minj] = temp
		#print("*{:}".format(c))
	 i range(n) range n minj = i minj i for j in range(i,n):
			if isbig(c[j], c[minj]) == 0:
				minj = j
		 j range(i,n) range i n if isbig(c[j], c[minj]) == 0:
				minj = j
		 isbig(c[j], c[minj]) == 0 isbig(c[j], c[minj]) isbig c[j] c j c[minj] c minj 0 minj = j minj j temp = c[i] temp c[i] c i c[i] = c[minj] c[i] c i c[minj] c minj c[minj] = temp c[minj] c minj temp return c c c c n n def isstable(unsort, sort):
	for i in range(n):
		for j in range(i+1,n):
			for k in range(n):
				for l in range(k+1,n):
					if isbig(unsort[i], unsort[j]) == 1 and unsort[i] == sort[l] and unsort[j] == sort[k]:
						return 0
	return 1 isstable for i in range(n):
		for j in range(i+1,n):
			for k in range(n):
				for l in range(k+1,n):
					if isbig(unsort[i], unsort[j]) == 1 and unsort[i] == sort[l] and unsort[j] == sort[k]:
						return 0
	 i range(n) range n for j in range(i+1,n):
			for k in range(n):
				for l in range(k+1,n):
					if isbig(unsort[i], unsort[j]) == 1 and unsort[i] == sort[l] and unsort[j] == sort[k]:
						return 0
	 j range(i+1,n) range i+1 i 1 n for k in range(n):
				for l in range(k+1,n):
					if isbig(unsort[i], unsort[j]) == 1 and unsort[i] == sort[l] and unsort[j] == sort[k]:
						return 0
	 k range(n) range n for l in range(k+1,n):
					if isbig(unsort[i], unsort[j]) == 1 and unsort[i] == sort[l] and unsort[j] == sort[k]:
						return 0
	 l range(k+1,n) range k+1 k 1 n if isbig(unsort[i], unsort[j]) == 1 and unsort[i] == sort[l] and unsort[j] == sort[k]:
						return 0
	 isbig(unsort[i], unsort[j]) == 1 and unsort[i] == sort[l] and unsort[j] == sort[k] isbig(unsort[i], unsort[j]) == 1 and unsort[i] == sort[l] isbig(unsort[i], unsort[j]) == 1 isbig(unsort[i], unsort[j]) isbig unsort[i] unsort i unsort[j] unsort j 1 unsort[i] == sort[l] unsort[i] unsort i sort[l] sort l unsort[j] == sort[k] unsort[j] unsort j sort[k] sort k return 0 0 return 1 1 unsort unsort sort sort for i in range(n):
	if i != n-1:
		print BubbleSort(cards1, n)[i],
	else:
		print BubbleSort(cards1, n)[i] i range(n) range n if i != n-1:
		print BubbleSort(cards1, n)[i],
	else:
		print BubbleSort(cards1, n)[i] i != n-1 i n-1 n 1 print BubbleSort(cards1, n)[i] (cards1, n) BubbleSort cards1 n i print BubbleSort(cards1, n)[i] (cards1, n) BubbleSort cards1 n i if isstable(cards, BubbleSort(cards1, n)) == 1:
	print("Stable")
else:
	print("Not stable") isstable(cards, BubbleSort(cards1, n)) == 1 isstable(cards, BubbleSort(cards1, n)) isstable cards BubbleSort(cards1, n) BubbleSort cards1 n 1 print("Stable") print "Stable" print("Not stable") print "Not stable" for i in range(n):
	if i != n-1:
		print SelectionSort(cards2, n)[i],
	else:
		print SelectionSort(cards2, n)[i] i range(n) range n if i != n-1:
		print SelectionSort(cards2, n)[i],
	else:
		print SelectionSort(cards2, n)[i] i != n-1 i n-1 n 1 print SelectionSort(cards2, n)[i] (cards2, n) SelectionSort cards2 n i print SelectionSort(cards2, n)[i] (cards2, n) SelectionSort cards2 n i if isstable(cards, SelectionSort(cards2, n)) == 1:
	print("Stable")
else:
	print("Not stable") isstable(cards, SelectionSort(cards2, n)) == 1 isstable(cards, SelectionSort(cards2, n)) isstable cards SelectionSort(cards2, n) SelectionSort cards2 n 1 print("Stable") print "Stable" print("Not stable") print "Not stable" cards1 = copy.deepcopy(cards) copy.deepcopy(cards) cards1 def SelectionSort(c, n):
	temp = 0
	for i in range(n):
		minj = i
		for j in range(i,n):
			if isbig(c[j], c[minj]) == 0:
				minj = j
		temp = c[i]
		c[i] = c[minj]
		c[minj] = temp
		#print("*{:}".format(c))
	return c def SelectionSort(c, n):
	temp = 0
	for i in range(n):
		minj = i
		for j in range(i,n):
			if isbig(c[j], c[minj]) == 0:
				minj = j
		temp = c[i]
		c[i] = c[minj]
		c[minj] = temp
		#print("*{:}".format(c))
	return c SelectionSort n = int(raw_input()) int(raw_input()) n def isstable(unsort, sort):
	for i in range(n):
		for j in range(i+1,n):
			for k in range(n):
				for l in range(k+1,n):
					if isbig(unsort[i], unsort[j]) == 1 and unsort[i] == sort[l] and unsort[j] == sort[k]:
						return 0
	return 1 def isstable(unsort, sort):
	for i in range(n):
		for j in range(i+1,n):
			for k in range(n):
				for l in range(k+1,n):
					if isbig(unsort[i], unsort[j]) == 1 and unsort[i] == sort[l] and unsort[j] == sort[k]:
						return 0
	return 1 isstable def BubbleSort(c, n):
	temp = 0
	for i in range(n):
		for j in reversed(range(i+1,n)):
			if isbig(c[j], c[j-1]) == 0:
				temp = c[j]
				c[j] = c[j-1]
				c[j-1] = temp
	return c def BubbleSort(c, n):
	temp = 0
	for i in range(n):
		for j in reversed(range(i+1,n)):
			if isbig(c[j], c[j-1]) == 0:
				temp = c[j]
				c[j] = c[j-1]
				c[j-1] = temp
	return c BubbleSort cards = raw_input().split() raw_input().split() cards cards2 = copy.deepcopy(cards) copy.deepcopy(cards) cards2 def isbig(card1, card2):
	if int(card1[1]) > int(card2[1]):
		return 2
	elif int(card1[1]) == int(card2[1]):
		return 1
	else:
		return 0 def isbig(card1, card2):
	if int(card1[1]) > int(card2[1]):
		return 2
	elif int(card1[1]) == int(card2[1]):
		return 1
	else:
		return 0 isbig
import copy

n = int(raw_input())
cards = raw_input().split()
cards1 = copy.deepcopy(cards)
cards2 = copy.deepcopy(cards)

def isbig(card1, card2):
	if int(card1[1]) > int(card2[1]):
		return 2
	elif int(card1[1]) == int(card2[1]):
		return 1
	else:
		return 0

def BubbleSort(c, n):
	temp = 0
	for i in range(n):
		for j in reversed(range(i+1,n)):
			if isbig(c[j], c[j-1]) == 0:
				temp = c[j]
				c[j] = c[j-1]
				c[j-1] = temp
	return c

def SelectionSort(c, n):
	temp = 0
	for i in range(n):
		minj = i
		for j in range(i,n):
			if isbig(c[j], c[minj]) == 0:
				minj = j
		temp = c[i]
		c[i] = c[minj]
		c[minj] = temp
		#print("*{:}".format(c))
	return c

def isstable(unsort, sort):
	for i in range(n):
		for j in range(i+1,n):
			for k in range(n):
				for l in range(k+1,n):
					if isbig(unsort[i], unsort[j]) == 1 and unsort[i] == sort[l] and unsort[j] == sort[k]:
						return 0
	return 1

for i in range(n):
	if i != n-1:
		print BubbleSort(cards1, n)[i],
	else:
		print BubbleSort(cards1, n)[i]

if isstable(cards, BubbleSort(cards1, n)) == 1:
	print("Stable")
else:
	print("Not stable")

for i in range(n):
	if i != n-1:
		print SelectionSort(cards2, n)[i],
	else:
		print SelectionSort(cards2, n)[i]

if isstable(cards, SelectionSort(cards2, n)) == 1:
	print("Stable")
else:
	print("Not stable")