Use the counting sort to order a list of strings associated with integers. If two strings are associated with the same integer, they must be printed in their original order, i.e. your sorting algorithm should be stable.  There is one other twist: strings in the first half of the array are to be replaced with the character - (dash, ascii 45 decimal).

Insertion Sort and the simple version of Quicksort are stable, but the faster in-place version of Quicksort is not since it scrambles around elements while sorting. 

Design your counting sort to be stable. 

Example 

$arrr=[[0,\text{'a'],[1,'b'],[0,'c'],[1,\text{'d'}]]$    

The first two strings are replaced with '-'.  Since the maximum associated integer is $1$, set up a helper array with at least two empty arrays as elements.  The following shows the insertions into an array of three empty arrays.

i	string	converted	list
0				[[],[],[]]
1 	a 	-		[[-],[],[]]
2	b	-		[[-],[-],[]]
3	c			[[-,c],[-],[]]
4	d			[[-,c],[-,d],[]]

The result is then printed: ${{-\mbox{c}}-\mbox{d}}$ . 

Function Description  

Complete the countSort function in the editor below.  It should construct and print the sorted strings.  

countSort has the following parameter(s):

string arr[n][2]: each arr[i] is comprised of two strings, x and s  

Returns 

- Print the finished array with each element separated by a single space.

Note: The first element of each $arr\left[i\right]$, $\boldsymbol{x}$, must be cast as an integer to perform the sort.  

Input Format

The first line contains $n$, the number of integer/string pairs in the array $\textbf{arr}$. 

Each of the next $n$ contains $x[i]$ and $s[i]$, the integers (as strings) with their associated strings.

Constraints

$1\leq n\leq1000000$ 

$n$ is even 

$1\leq|s|\leq10$ 

$0\leq x<100,x\in ar$ 

$s[i]$ consists of characters in the range $\text{ascii[a-z]}$

Output Format

Print the strings in their correct order, space-separated on one line. 

Sample Input
20
0 ab
6 cd
0 ef
6 gh
4 ij
0 ab
6 cd
0 ef
6 gh
0 ij
4 that
3 be
0 to
1 be
5 question
1 or
2 not
4 is
2 to
4 the

Sample Output
- - - - - to be or not to be - that is the question - - - -

Explanation

The correct order is shown below. In the array at the bottom, strings from the first half of the original array were replaced with dashes.

0 ab
0 ef
0 ab
0 ef
0 ij
0 to
1 be
1 or
2 not
2 to
3 be
4 ij
4 that
4 is
4 the
5 question
6 cd
6 gh
6 cd
6 gh

sorted = [['-', '-', '-', '-', '-', 'to'], ['be', 'or'], ['not', 'to'], ['be'], ['-', 'that', 'is', 'the'], ['question'], ['-', '-', '-', '-'], [], [], [], []]

Source: hackerrank | Difficulty: MEDIUM
Tags: Sorting


Solutions:
n = int(input())
ar = []
for i in range(0, n):
	data = input().strip().split(' ')
	ar.append((int(data[0]), data[1]))
c = [0] * 100
for a in ar:
	c[a[0]] += 1
c1 = [0] * 100
for x in range(1, 100):
	c1[x] = c1[x - 1] + c[x - 1]
s = ['-'] * n
for i in range(0, n):
	if i >= n / 2:
		s[c1[ar[i][0]]] = ar[i][1]
	c1[ar[i][0]] += 1
print(' '.join(s))


import sys
testcase = int(input())
strings = ['' for i in range(testcase)]
for i in range(testcase):
	temp = [j for j in input().split()]
	in1 = int(temp[0])
	if i < testcase / 2:
		temp[1] = '-'
	strings[in1] += temp[1] + ' '
for j in strings:
	sys.stdout.write(j)


def main():
	size = int(input())
	array = []
	for i in range(0, int(size / 2)):
		line = input()
		array.append((int(line.split(' ')[0]), '-'))
	for i in range(int(size / 2), size):
		line = input()
		array.append((int(line.split(' ')[0]), line.split(' ')[1]))
	count = [0] * 100
	for item in array:
		count[item[0]] += 1
	total = 0
	for i in range(0, len(count)):
		old_val = count[i]
		count[i] = total
		total = total + old_val
	output = [''] * size
	for item in array:
		output[count[item[0]]] = item[1]
		count[item[0]] += 1
	for item in output:
		print(item, end=' ')
main()


n = int(input())
counts = {i: [] for i in range(100)}
for i in range(n):
	curr = input().split()
	key = int(curr[0])
	if i < n // 2:
		value = '-'
	else:
		value = curr[1]
	counts[key].append(value)
for i in range(100):
	for j in counts[i]:
		print(j, end=' ')
print()


size = int(input())
data = {}
numbers = []
for i in range(size):
	(no, line) = input().split(' ')
	no = int(no)
	if i < size / 2:
		line = '-'
	if not data.get(no):
		data[no] = []
	data[no].append(line)
	numbers.append(no)
a = [0 for i in range(100)]
for i in numbers:
	a[i] += 1
result = []
for i in range(len(a)):
	for string in data.get(i, []):
		result.append(string)
print(' '.join(result))


import sys
w = []
for i in range(100):
	w.append([])
n = int(sys.stdin.readline().strip())
for i in range(n):
	(x, txt) = sys.stdin.readline().strip().split(' ')
	x = int(x)
	if i < n // 2:
		txt = '-'
	w[x].append(txt)
first = True
for i in range(100):
	for txt in w[i]:
		if first:
			first = False
		else:
			print(' ', end='')
		print(txt, end='')


n = int(input())
ar = []
for i in range(n):
	inp = input().strip().split()
	ar.append([int(inp[0]), i, inp[1]])
for i in range(n // 2):
	ar[i][2] = '-'
ar.sort()
for e in ar:
	print(e[2], end=' ')


l = ['' for i in range(0, 100)]
n = int(input())
for i in range(0, n):
	(x, y) = input().split()
	x = int(x)
	if i < n / 2:
		y = '-'
	if '' == l[x]:
		l[x] = y
	else:
		l[x] += ' ' + y
for i in range(0, 100):
	if l[i] != '':
		print(l[i], end=' ')


n = int(input())
half = n / 2
words = [[] for x in range(100)]
for i in range(n):
	(num, word) = input().split()
	if i < half:
		word = '-'
	words[int(num)].append(word)
res = []
for word in words:
	res += word
print(' '.join(res))


n = int(input())
count = [[] for i in range(100)]
for i in range(n):
	(num, l) = input().split()
	count[int(num)].append((l, i))
print(' '.join([word if index >= n / 2 else '-' for num in count for (word, index) in num]))


def key1(lst):
	return lst[0]
n = int(input())
lst = []
for i in range(n):
	inp = input().split()
	if i < n / 2:
		pn = 0
	else:
		pn = 1
	lst.append([int(inp[0]), inp[1], pn])
ar = []
for i in range(100):
	ar.append([])
for l in lst:
	ar[l[0]].append(l)
for l in ar:
	for i in l:
		if i[2]:
			print(i[1], end=' ')
		else:
			print('-', end=' ')


def start(a):
	return a[0]
array_length = int(input())
num = []
num_value = []
for value in range(array_length):
	(_num, _value) = input().split()
	num.append(int(_num))
	num_value.append(_value)
for value in range(array_length // 2):
	num_value[value] = '-'
new = []
for value in range(array_length):
	new.append((num[value], num_value[value]))
new = sorted(new, key=start)
_li = []
for value in new:
	_li.append(value[1])
print(' '.join(_li))


from itertools import islice
import sys
n = int(input())
sr = ['' for i in range(100)]
ar = [0 for i in range(100)]
c = 0
ls = islice(sys.stdin, n)
for i in ls:
	st = i.strip().split(' ')
	x = int(st[0])
	s = st[1]
	l = 1
	if c >= n / 2:
		sr[x] = sr[x] + ' ' + s if len(sr[x]) > 0 else s
		l = 0
	ar[x] += l
	c += 1
for i in range(100):
	for j in range(ar[i]):
		print('-', end=' ')
	print(sr[i], end=' ')


SIZE = 100
strings = {}
for i in range(SIZE):
	strings[i] = ''
n = int(input())
mid = int(n // 2)
import sys
for i in range(n):
	(_val, s) = input().split()
	val = int(_val)
	if i < mid:
		s = '-'
	strings[val] += s + ' '
for i in range(SIZE):
	print(strings[i], end='')


import sys

def print_list(data):
	for element in data:
		print(element[1], end=' ')
	print()
sizeOfList = int(sys.stdin.readline())
data = []
for index in range(sizeOfList):
	raw = sys.stdin.readline().split()
	if index < sizeOfList / 2:
		data.append((int(raw[0]), '-'))
	else:
		data.append((int(raw[0]), raw[1]))
counter = [0] * 100
for element in data:
	counter[element[0]] += 1
for index in range(1, len(counter)):
	counter[index] = counter[index] + counter[index - 1]
result = [0] * len(data)
for element in reversed(data):
	result[counter[element[0]] - 1] = element
	counter[element[0]] -= 1
print_list(result)


n = int(input())
ar = []
counts = 100 * [0]
for iw in range(n):
	(si, s) = input().split()
	i = int(si)
	ar.append((i, s if iw >= n // 2 else '-'))
	counts[i] += 1
offsets = 100 * [0]
tot = 0
for i in range(100):
	offsets[i] = tot
	tot += counts[i]
sorted = n * ['']
for (i, s) in ar:
	sorted[offsets[i]] = s
	offsets[i] += 1
print(' '.join(sorted))


testCases = int(input())
half = testCases // 2
listLetters = []
listNum = []
while testCases:
	nk = input().split(' ')
	listNum.append(int(nk[0]))
	if testCases > half:
		listLetters.append('-')
	else:
		listLetters.append(nk[1])
	testCases -= 1
(list1, list2) = (list(t) for t in zip(*sorted(zip(listNum, listLetters))))
strout = ''
sortedRes = sorted(zip(listNum, listLetters), key=lambda x: x[0])
for v in sortedRes:
	strout += v[1] + ' '
strout = strout.strip()
print(strout, end='')


import sys

def mToString(mArray):
	startStr = ''
	for el in mArray:
		startStr = startStr + str(el) + ' '
	if len(startStr) == 0:
		startStr = ' '
	return startStr[:-1]

def getNum(line):
	return int(line.split()[0])
lines = []
for line in sys.stdin:
	lines.append(line)
n = int(lines[0])
data = lines[1:]
nums = list(map(getNum, data))
inputArray = {}
for i in range(n):
	num = data[i].split()[0]
	if i < int(n / 2):
		word = '-'
	else:
		word = data[i].split()[1]
	if num in inputArray.keys():
		inputArray[num] = inputArray[num] + ' ' + word
	else:
		inputArray[num] = word
countArray = [0] * 100
for el in nums:
	countArray[el] = countArray[el] + 1
sortedArray = []
finalString = ''
for i in range(100):
	if countArray[i] > 0:
		i = str(i)
		finalString = finalString + inputArray[i] + ' '
print(finalString)


n = int(input())
arr = []
for i in range(n):
	(x, s) = str(input()).split()
	x = int(x)
	if 2 * i < n:
		s = '-'
	arr.append((x, s))
buckets = [[] for i in range(100)]
for (x, s) in arr:
	buckets[x].append(s)
strings = []
for bucket in buckets:
	strings += bucket
print(' '.join(strings))


import sys
import collections
n = int(input())
dic = {}
array = [None] * n
for i in range(n):
	(z, y) = input().split()
	z = int(z)
	array[i] = [z, y]
	if z in dic:
		dic[z].append(y)
	else:
		dic[z] = [y]

def countsort(ar):
	counts = [0] * 100
	for x in ar:
		counts[x[0]] += 1
	return counts

def countsortdic(dic):
	counts = [0] * 100
	for x in dic:
		counts[x] += len(dic[x])
	return counts

def inorder(array):
	lst = []
	for i in range(len(array)):
		for x in range(array[i]):
			lst.append(i)
	return lst

def totfreqs(dic):
	results = [0] * 100
	if 0 in dic:
		results[0] = len(dic[0])
	for i in range(1, 100):
		if i in dic:
			results[i] += len(dic[i]) + results[i - 1]
		else:
			results[i] += results[i - 1]
	return results

def stablecountsort(finals, first, second):
	plc = []
	counts = collections.defaultdict(int)
	for x in finals:
		if counts[x] >= first[x] and second[x] != 0:
			plc.append(dic[x][counts[x]])
			counts[x] += 1
		else:
			plc.append('-')
			counts[x] += 1
	return plc
finals = inorder(countsortdic(dic))
first = countsort(array[:int(n / 2)])
second = countsort(array[int(n / 2):])
stable = stablecountsort(finals, first, second)
print(' '.join(map(str, stable)))


size = int(input())
dict = []
assert 1 <= size <= 1000000
for i in range(0, size):
	(nums, strs) = input().split()
	dict.append([int(nums), strs])
for x in range(0, len(dict) // 2):
	dict[x][1] = '-'
answer = ''
for x in sorted(dict, key=lambda x: x[0]):
	answer += x[1] + ' '
print(answer.strip())


f = lambda : input().strip().split(' ')
n = int(f()[0])
m = int(n / 2)
A = [0] * n
for i in range(m):
	line = f()
	A[i] = (int(line[0]), '-')
for i in range(m, n):
	line = f()
	A[i] = (int(line[0]), line[1])
C = [0] * n
for i in range(n):
	C[A[i][0]] += 1
for i in range(n - 1):
	C[i + 1] += C[i]
D = [0] * n
for i in range(n - 1, -1, -1):
	v = A[i]
	D[C[v[0]] - 1] = v[1]
	C[v[0]] -= 1
print(str(D).replace(',', '').replace("'", '')[1:-1])


n = int(input())
xarr = [None] * 100
for ni in range(n):
	(x, s) = input().split()
	x = int(x)
	if xarr[x] == None:
		xarr[x] = [0, []]
	xarr[x][0] += 1
	xarr[x][1].append('-' if ni < n // 2 else s)
curstart = 0
for i in range(100):
	if xarr[i] != None:
		(xarr[i][0], curstart) = (curstart, curstart + xarr[i][0])
print(' '.join([' '.join(x[1]) for x in xarr if x != None]))


import sys

def counting(arr, s):
	appearences = []
	for x in range(100):
		appearences.append(0)
	for value in arr:
		appearences[value] += 1
	return appearences
size = int(sys.stdin.readline().strip())
array = []
for x in range(size):
	array.append(sys.stdin.readline().strip())
array = [i.split() for i in array]
numbers = [int(i[0]) for i in array]
arr = counting(numbers, size)
counter = 0
sorted_arr = []
for x in range(100):
	counter += arr[x]
	sorted_arr.append(counter)
result = []
help_arr = []
for x in array:
	result.append('')
for x in range(100):
	help_arr.append(0)
for x in range(size):
	if int(array[x][0]) == 0:
		place = 0
	else:
		place = sorted_arr[int(array[x][0]) - 1]
	i = help_arr[int(array[x][0])]
	if x < size // 2:
		result[place + i] = '-'
	else:
		result[place + i] = array[x][1]
	help_arr[int(array[x][0])] += 1
print(' '.join(result))


n = int(input())
ar = []
for k in range(n):
	(i, s) = input().split()
	ar.append((int(i), s))
count = [0] * n
for e in ar:
	count[e[0]] += 1
total = 0
for (i, e) in enumerate(count):
	count[i] = total
	total += e
sar = [0] * n
for (k, (i, s)) in enumerate(ar):
	sar[count[i]] = s if k >= n / 2 else '-'
	count[i] += 1
print(' '.join(sar))


N = int(input())
strings = ['' for i in range(100)]
for i in range(N):
	[n, string] = [e for e in str(input()).split()]
	if i < N / 2:
		string = '-'
	if strings[int(n)] != '':
		strings[int(n)] += ' ' + string
	else:
		strings[int(n)] += string
tmp = ''
for (i, s_string) in enumerate(strings):
	if s_string == '':
		continue
	if i != 0:
		tmp += ' ' + s_string
	else:
		tmp += s_string
print(tmp)


import sys
arr = []
N = int(sys.stdin.readline())
for i in range(N):
	(num, val) = sys.stdin.readline().split()
	num = int(num)
	if i < N / 2:
		val = '-'
	arr.append([num, i, val])
arr.sort()
print(' '.join((val for (num, i, val) in arr)))


import sys, math, copy
data = sys.stdin.readlines()
N2 = int(data[0]) // 2

def parse(i, line):
	(n, s) = line.split()
	return (int(n), s if i >= N2 else '-')
a = [parse(i, line) for (i, line) in enumerate(data[1:])]
o = []
for i in range(100):
	o.extend([s for (n, s) in a if n == i])
print(' '.join(o))


N = int(input())
ls = []
res = ['' for i in range(0, N)]
d = {}
helper = [0 for i in range(0, 100)]
helper1 = [0 for i in range(0, 100)]
for i in range(0, N):
	(a, b) = input().split()
	a = int(a)
	if i < N / 2:
		b = '-'
	if a in d:
		d[a] = d[a] + 1
	else:
		d[a] = 1
	helper[a] = helper[a] + 1
	ls.append([a, b])
helper1[0] = helper[0]
for i in range(1, 100):
	helper1[i] = helper[i] + helper1[i - 1]
for i in ls:
	idx = helper1[i[0]] - helper[i[0]]
	res[idx] = i[1]
	helper[i[0]] = helper[i[0]] - 1
print(' '.join([x for x in res]))


buckets = {}
data = {}
for i in range(100):
	buckets[i] = 0
	data[i] = []
n = int(input())
for i in range(n):
	(num_str, data_str) = input().split(' ')
	if i < n / 2:
		data[int(num_str)].append('-')
	else:
		data[int(num_str)].append(data_str)
final = []
for i in range(100):
	final.extend(data[i])
print(' '.join(map(str, final)))


n = int(input())
ar = [0] * n
source = []
for i in range(n):
	parts = input().split()
	parts[0] = int(parts[0])
	if i < n / 2:
		parts[1] = '-'
	source.append(parts)
	k = parts[0]
	ar[k] += 1
L = 0
help = [0]
for e in ar:
	L += e
	help.append(L)
target = [None] * n
for e in range(len(source)):
	index = source[e][0]
	target[help[index]] = source[e][1]
	help[index] += 1
print(' '.join(target))


from collections import defaultdict
n = int(input())
nbs = []
indexes = defaultdict(lambda : [])
for i in range(n // 2):
	tmp = input().split()
	index = int(tmp[0])
	indexes[index].append(i)
	nbs.append((index, '-'))
for i in range(n // 2):
	tmp = input().split()
	index = int(tmp[0])
	indexes[index].append(n // 2 + i)
	nbs.append((index, tmp[1]))
ret = []
for i in range(max(indexes) + 1):
	for k in indexes[i]:
		ret.append(nbs[k][1])
print(' '.join(ret))


n = eval(input())
l = [input().split() for i in range(n)]
l = [[int(l[i][0]), '-' if i < n / 2 else l[i][1]] for i in range(n)]
l.sort(key=lambda k: k[0])
out = [l[i][1] for i in range(n)]
print(' '.join(out))


from collections import deque
n = int(input())
n2 = n // 2
w = {}
c = {}
for i in range(n):
	(x, word) = input().strip().split()
	x = int(x)
	if i < n2:
		word = '-'
	if x not in w:
		w[x] = deque()
	w[x].append(word)
	c[x] = c.get(x, 0) + 1
for i in range(100):
	if i in c:
		for count in range(c[i]):
			print(w[i].popleft(), end=' ')


N = int(input())
counts = dict()
array_data = dict()
for i in range(N):
	(v, s) = input().split(' ')
	v = int(v)
	counts[v] = counts.get(v, 0) + 1
	if i < N // 2:
		s = '-'
	if v in array_data:
		array_data[v].append(s)
	else:
		array_data[v] = [s]
total = 0
out = []
for i in range(100):
	out.append(' '.join(array_data.get(i, [])))
print(' '.join(out))


n = int(input())
arr = []
for i in range(n):
	arr.append(tuple(str(input()).split()))
helper_arr = []
for i in range(100):
	helper_arr.append([])
output_arr = []
for i in range(n):
	(value, s) = arr[i]
	if i < n / 2:
		s = '-'
	helper_arr[int(value)].append(s)
for i in helper_arr:
	for j in i:
		output_arr.append(j)
print(' '.join([str(i) for i in output_arr]))


import collections

def tc(n, arr):
	d = collections.defaultdict(list)
	for i in range(n):
		(k, v) = arr[i].split()
		if i < n // 2:
			d[int(k)].append('-')
		else:
			d[int(k)].append(v)
	od = collections.OrderedDict(sorted(d.items()))
	print(' '.join([' '.join(l) for l in od.values()]))
n = int(input())
arr = []
for _ in range(n):
	arr.append(input())
tc(n, arr)


from collections import OrderedDict
n = int(input())
ar = {}
half = n // 2
for i in range(half):
	(integer, string) = input().split(' ')
	ar[i] = (int(integer), '-')
for i in range(half, n):
	(integer, string) = input().split(' ')
	ar[i] = (int(integer), string)
values = OrderedDict()
for i in range(100):
	values[i] = []
for x in range(n):
	values[ar[x][0]].append(ar[x][1])
final = [item for sublist in values for item in values[sublist]]
print(' '.join(map(str, final)))


from collections import defaultdict
MAXNUM = 100

def count_numbers(lst):
	return [lst.count(n) for n in range(MAXNUM)]

def sort(lst):
	sorted_lst = []
	for (i, c) in enumerate(lst):
		if c != 0:
			sorted_lst.extend((i for _ in range(c)))
	return sorted_lst

def count_less_or_equal(lst):
	return [sum(lst[:i + 1]) for (i, _) in enumerate(lst)]

def associate(sorted_list, words, helper_list):
	output = []
	(curr_index, i) = (0, 0)
	while curr_index < len(sorted_list):
		output.extend(words[sorted_list[curr_index]])
		curr_index = helper_list[i]
		i += 1
	return output
n = int(input())
(numbers, words) = ([], defaultdict(list))
for i in range(n):
	(num, word) = input().split()
	if i < n / 2:
		word = '-'
	numbers.append(int(num))
	words[int(num)].append(word)
count = count_numbers(numbers)
helper_lst = count_less_or_equal(count)
sorted_numbers = sort(count)
print(' '.join((word for word in associate(sorted_numbers, words, helper_lst))))


len_sort = int(input())
max = 0
dict = {}
list = []
for i in range(len_sort):
	render = input().split(' ')
	num = int(render[0])
	string = render[1]
	if num > max:
		max = num
	if num in dict.keys():
		if i < len_sort // 2:
			dict[num].append('-')
		else:
			dict[num].append(string)
	elif i < len_sort // 2:
		dict[num] = ['-']
	else:
		dict[num] = [string]
for i in range(max + 1):
	for j in dict[i]:
		list.append(j)
for i in range(len(list)):
	print(list[i], end=' ')


n = int(input())
d = dict()
for i in range(n):
	(key, value) = input().split(' ')
	key = int(key)
	if key not in d:
		d[key] = []
	if i < int(n / 2):
		value = '-'
	d[key].append(value)
for i in range(len(d)):
	print(' '.join(d[i]), end=' ')


N = int(input())
X = [[] for i in range(100)]
for i in range(N):
	(k, v) = input().split()
	X[int(k)].append(v if i >= N / 2 else '-')
for i in range(100):
	for j in X[i]:
		print(j, end=' ')


n = int(input())
ar = []
for _ in range(n):
	(a, b) = input().split()
	ar.append((int(a), b))
count = [[0] for _ in range(100)]
for i in range(n):
	count[ar[i][0]][0] += 1
	if i >= n / 2:
		count[ar[i][0]].append(ar[i][1])
	else:
		count[ar[i][0]].append('-')
for element in count:
	if element[0] != 0:
		print(' '.join(element[1:]), end=' ')


n = int(input())
m = 100
A = [[] for x in range(m)]
nDivTwo = n / 2
for i in range(n):
	line = input().strip().split()
	A[int(line[0])].append('-' if i < nDivTwo else line[1])
msg = []
for L in A:
	for s in L:
		msg.append(s)
print(' '.join(msg))


l = [[] for i in range(100)]
n = int(input())
n = n >> 1
for i in range(n):
	x = int(input().split()[0])
	l[x].append('-')
for i in range(n):
	(x, s) = input().split(maxsplit=1)
	l[int(x)].append(s)
for i in l:
	for j in i:
		print(j, end=' ')


import sys
DEV = False

def Inc(Max_, Start_=0, Increment_=1):
	for num in range(Start_, Max_, Increment_):
		yield num

def Keys(Dict_, Sort_=True):
	dict_it = Dict_.keys()
	if Sort_:
		dict_it = sorted(dict_it)
	return dict_it
if DEV:
	f = open('test_data.txt', 'r')
	N = int(f.readline().strip())
else:
	N = int(input().strip())
in_ra = [None for num in Inc(N)]
str_dict = {}
mid = N // 2
for idx in Inc(N):
	if DEV:
		pair = f.readline().strip().split()
	else:
		pair = input().strip().split()
	pair[0] = int(pair[0])
	if pair[0] in str_dict:
		str_dict[pair[0]].append(idx)
	else:
		str_dict[pair[0]] = [idx]
	if idx < mid:
		pair[1] = '-'
	in_ra[idx] = pair[1]
if DEV:
	f.close()
out_str = ''
for key in Keys(str_dict):
	for str_idx in str_dict[key]:
		out_str += '{0} '.format(in_ra[str_idx])
print(out_str)


from operator import itemgetter
n = int(input())
a = [0] * n
for i in range(n // 2):
	(f, l) = input().split()
	a[i] = (int(f), '-')
for i in range(n // 2, n):
	(f, l) = input().split()
	a[i] = (int(f), l)
a.sort(key=itemgetter(0))
print(' '.join((b for (a, b) in a)))


n = int(input())
d = dict()
for i in range(n):
	(key, value) = input().split(' ')
	key = int(key)
	if key not in d:
		d[key] = []
	if i < int(n / 2):
		value = '-'
	d[key].append(value)
for i in range(len(d)):
	print(' '.join(d[i]), end=' ')


from collections import defaultdict
listSize = int(input())
occurrenceValueDict = defaultdict(lambda : [])
occurrences = defaultdict(lambda : 0)
for i in range(listSize):
	inputLineList = input().split()
	key = int(inputLineList[0])
	occurrences[key] += 1
	occurrenceValueDict[key].append((i, inputLineList[1]))
for i in range(100):
	for occurrence in range(occurrences[i]):
		valueDict = occurrenceValueDict[i][occurrence]
		index = valueDict[0]
		if index < listSize / 2:
			print('-', end=' ')
		else:
			print(valueDict[1], end=' ')


from sys import stdin
records_count = int(stdin.readline())
counts = [0] * 100
records = []
record_index_top_half = records_count // 2
for record_number in range(records_count):
	(n, data) = stdin.readline().split()
	n = int(n)
	if record_index_top_half <= record_number:
		records.append((n, data))
	else:
		records.append((n, '-'))
	counts[n] += 1
count_total = 0
for i in range(100):
	count = counts[i]
	counts[i] = count_total
	count_total += count
output = ['+'] * records_count
for record_number in range(records_count):
	(idx, data) = records[record_number]
	count = counts[idx]
	output[count] = data
	counts[idx] += 1
print(' '.join(output))


N = int(input())
Count = [0 for i in range(0, 100)]
CountStrings = [[] for i in range(0, 100)]
for i in range(0, N):
	(x, s) = input().split()
	if 2 * i < N:
		s = '-'
	x = int(x)
	Count[x] = Count[x] + 1
	CountStrings[x].append(s)
res = []
for i in range(0, 100):
	C = Count[i]
	if C > 0:
		res.append(' '.join(CountStrings[i]))
print(' '.join(res))


import sys
words = int(sys.stdin.readline())
dic = {}
for i in range(words // 2):
	wordInfo = sys.stdin.readline().strip().split()
	count = int(wordInfo[0])
	word = wordInfo[1]
	if count in dic:
		dic[count].append(word)
	else:
		dic[count] = [word]
for keys in dic:
	dic[keys].append('XXX')
for i in range(words // 2):
	wordInfo = sys.stdin.readline().strip().split()
	count = int(wordInfo[0])
	word = wordInfo[1]
	if count in dic:
		dic[count].append(word)
	else:
		dic[count] = ['XXX']
		dic[count].append(word)
keys = sorted(dic.keys())
for k in keys:
	lst = dic[k]
	midway = False
	for words in lst:
		if words == 'XXX':
			midway = True
		elif midway == False:
			sys.stdout.write('- ')
		else:
			sys.stdout.write(words + ' ')


def countingSort(numArray, stringArray):
	counts = count(numArray, stringArray)
	output = []
	for i in range(len(counts)):
		for j in counts[i]:
			output.append(j)
	return output

def count(numArray, stringArray):
	counts = []
	for i in range(100):
		counts.append([])
	for i in range(len(numArray)):
		counts[numArray[i]].append(stringArray[i])
	return counts

def printArray(array):
	output = ''
	for a in array:
		output += str(a) + ' '
	print(output)
lengthOfArray = int(input())
numArray = []
stringArray = []
for i in range(lengthOfArray):
	theInput = input().split()
	numArray.append(int(theInput[0]))
	if i < lengthOfArray / 2:
		stringArray.append('-')
	else:
		stringArray.append(theInput[1])
printArray(countingSort(numArray, stringArray))


n = int(input())
arr_input_total = []
for i in range(n):
	(num, string) = input().split()
	arr_input_total.append((int(num), string))
hist = [0 for _ in range(100)]
for k in arr_input_total:
	hist[k[0]] += 1
total = 0
for k in range(len(hist)):
	old_count = hist[k]
	hist[k] = total
	total += old_count
output = ['-' for _ in range(n)]
for k in range(n // 2):
	temp = arr_input_total[k]
	hist[temp[0]] += 1
for k in range(n // 2, n):
	temp = arr_input_total[k]
	output[hist[temp[0]]] = temp[1]
	hist[temp[0]] += 1
print(' '.join(output))


rs = {}
for i in range(100):
	rs.update({i: []})
n = int(input())
for t in [1] * (n // 2):
	(num, string) = input().split()
	num = int(num)
	rs[num].append('-')
for t in [1] * (n // 2):
	(num, string) = input().split()
	num = int(num)
	rs[num].append(string)
for i in range(100):
	for string in rs[i]:
		print(string, end=' ')


from collections import defaultdict
count_map = defaultdict(lambda : 0)
n = int(input().strip())
content = []
for i in range(0, n):
	(key, value) = input().strip().split(' ')
	key = int(key)
	count_map[key] = count_map[key] + 1
	content.append((key, '-' if i < n / 2 else value))
count = 0
for key in sorted(count_map.keys()):
	temp = count_map[key]
	count_map[key] = count
	count += temp
result = [None] * n
for (k, v) in content:
	result[count_map[k]] = v
	count_map[k] += 1
print(' '.join(result))


n = int(input())
k = []
for i in range(n):
	elem = input()
	(a, b) = elem.split()
	a = int(a)
	k.append((a, i, b))
ris = sorted(k, key=lambda x: x[0])
ris = [str(c) if b > n / 2 - 1 else '-' for (a, b, c) in ris]
print(' '.join(ris))


in_len = int(input())
k = 100
d = {}
for idx in range(in_len):
	kv_str_arr = input().split()
	val = (kv_str_arr[1], idx)
	key = int(kv_str_arr[0])
	if key not in d:
		d[key] = [val]
	else:
		d[key].append(val)
print_len = in_len / 2
out_arr = []
for idx in range(k):
	if idx in d:
		items = d[idx]
		for item in items:
			if item[1] < print_len:
				out_arr += '-'
			else:
				out_arr += [item[0]]
print(str(out_arr).replace('[', '').replace(']', '').replace(',', '').replace("'", ''))


from collections import defaultdict

def counting_sort(ar):
	freqs = defaultdict(lambda : [])
	for tup in ar:
		(o, i, word) = tup
		freqs[o].append(tup)
	order = []
	for i in range(100):
		order.extend(freqs[i])
	return order
n = int(input())
ar = []
for i in range(n):
	(num, word) = input().split()
	ar.append((int(num), i, word))
ar = counting_sort(ar)
words = [word if i >= len(ar) / 2 else '-' for (o, i, word) in ar]
print(' '.join(words))


import collections
c = collections.defaultdict(list)
lines = int(input())
for i in range(lines):
	line = input().split()
	n = int(line[0])
	word = line[1]
	c[n].append((i, word))
output = []
for n in range(100):
	if n in c:
		words = c[n]
		for (i, word) in words:
			if i < lines // 2:
				output.append('-')
			else:
				output.append(word)
print(' '.join(output))


n = int(input().strip())
(numbers, strings) = ([], [])
for _ in range(n):
	(x, s) = input().strip().split()
	numbers.append(int(x))
	strings.append(s)
output = [[] for _ in range(100)]
half = n / 2
for i in range(n):
	if i < half:
		output[numbers[i]].append('-')
	else:
		output[numbers[i]].append(strings[i])
combined = []
for o in output:
	if o:
		combined.extend(o)
print(' '.join(combined))


def run():
	n = int(input())
	origar = [''] * n
	ar = [0] * 100
	for i in range(n):
		line = input().strip().split()
		x = int(line[0])
		ar[x] += 1
		origar[i] = (x, line[1] if i >= n // 2 else '-')
	for i in range(1, 100):
		ar[i] += ar[i - 1]
	ar = [0] + ar
	finalar = [''] * n
	for elem in origar:
		finalar[ar[elem[0]]] = elem[1]
		ar[elem[0]] += 1
	for x in finalar:
		print(x, end=' ')
run()


S = 100

def count(l):
	counts = [0] * S
	for el in l:
		counts[el] += 1
	return counts

def counting_sort(l):
	result = []
	for (i, number) in enumerate(count(l)):
		while number:
			result.append(i)
			number -= 1
	return result

def get_helper_array(l):
	s = 0
	result = []
	for c in count(l):
		result.append(s)
		s += c
	return result
N = int(input())
ar = [input() for i in range(N)]
helper_array = get_helper_array((int(x.split()[0]) for x in ar))
result = [None] * N
for (i, el) in enumerate(ar):
	(key, value) = el.split()
	key = int(key)
	if i < N // 2:
		value = '-'
	insert_to = helper_array[key]
	result[insert_to] = value
	helper_array[key] += 1
print(*result)


def main():
	n = int(input())
	data = []
	for i in range(n):
		line = str(input())
		flag = i + 1 <= n / 2
		data.append([int(line.split()[0]), line.split()[1], not flag])
	s = []
	d = sorted(data, key=lambda x: x[0])
	for i in range(len(d)):
		if d[i][2]:
			s.append(d[i][1])
		else:
			s.append('-')
	print(' '.join(s))
main()


import sys
n = int(sys.stdin.readline())
counts = [0] * 100
words = [[] for i in range(0, 100)]
for i in range(0, n):
	(x, s) = sys.stdin.readline().split(' ')
	x = int(x)
	s = s.strip()
	if 2 * i < n:
		s = '-'
	counts[x] += 1
	words[x].append(s)
out = []
for i in range(0, 100):
	for j in range(0, counts[i]):
		out.append(words[i].pop(0))
print(' '.join(out))


n = int(input())
A = []
for i in range(n):
	x = input().split()
	A.append(x)
B = [0] * 100
for x in A:
	B[int(x[0])] += 1
for i in range(100):
	if i != 0:
		B[i] += B[i - 1]
C = [['-1', '-']] * n
for i in reversed(range(n // 2, n)):
	C[B[int(A[i][0])] - 1] = A[i]
	B[int(A[i][0])] -= 1
print(' '.join((x[1] for x in C)))


n = int(input())
count = [0] * 100
x = []
for i in range(n):
	l = input().split()
	if i < n // 2:
		x.append((int(l[0]), '-'))
	else:
		x.append((int(l[0]), l[1]))
for i in x:
	count[i[0]] += 1
for i in range(1, len(count)):
	count[i] += count[i - 1]
sorted = [0] * len(x)
for i in range(len(x) - 1, -1, -1):
	sorted[count[x[i][0]] - 1] = x[i]
	count[x[i][0]] -= 1
print(' '.join(map(lambda x: str(x[1]), sorted)))


def counting_sort(ar):
	x_only = [x for (x, __) in ar]
	count = [0] * 100
	for x in x_only:
		count[x] += 1
	x_s_dict = {}
	for x in set(x_only):
		x_s_dict[x] = []
	for (x, s) in ar:
		x_s_dict[x].append(s)
	sorted_ar = []
	for (i, c) in enumerate(count):
		if c != 0:
			sorted_ar += x_s_dict[i]
	print(' '.join(sorted_ar))
n = int(input())
ar = []
for i in range(n):
	(x, s) = input().split()
	ar.append((int(x), s))
for i in range(n // 2):
	ar[i] = (ar[i][0], '-')
counting_sort(ar)


from collections import defaultdict
n = int(input())
d = defaultdict(list)
m = 0
for x in range(n):
	(num, string) = input().split()
	m = m if m > int(num) else int(num)
	d[int(num)].append(string)
	d[int(num)].append(x)
for x in range(m + 1):
	for y in range(0, len(d[x]), 2):
		if d[x][y + 1] < n / 2:
			print('-', end=' ')
		else:
			print(d[x][y], end=' ')


N = int(input())
sorted_arr = [None] * 100
for i in range(N):
	(num, text) = input().split()
	if i < N // 2:
		text = '-'
	bucket = int(num)
	if sorted_arr[bucket] is None:
		sorted_arr[bucket] = [text]
	else:
		sorted_arr[bucket].append(text)
print(' '.join([x for string_array in sorted_arr if string_array for x in string_array]))


def counting_sort(place, letters):
	half = len(letters) // 2
	letters[:half] = '-' * half
	sort = sorted(zip(place, letters), key=lambda x: x[0])
	answer = [v for (k, v) in sort]
	return ' '.join(answer)
num_strs = int(input())
(place, letters) = ([], [])
for i in range(num_strs):
	a = input()
	(p, l) = a.split(' ')
	place.append(int(p))
	letters.append(l)
print(counting_sort(place, letters))


n = int(input())
k = 100
ar = []
count = [0] * k
for i in range(n):
	split_items = input().split(' ')
	x = int(split_items[0])
	s = split_items[1]
	count[x] += 1
	ar.append([x, s])

def create_keys(count):
	total = 0
	for i in range(k):
		oldCount = count[i]
		count[i] = total
		total += oldCount
	return count

def perform_sort():
	output = [0] * n
	for tup in ar:
		key = tup[0]
		output[count[key]] = tup
		count[key] += 1
	return output

def twist(ar):
	dash_end = int(n / 2)
	for i in range(dash_end):
		ar[i][1] = '-'
	return ar
ar = twist(ar)
count = create_keys(count)
output = perform_sort()
out_str = []
for tup in output:
	out_str.append(tup[1])
print(' '.join(out_str))


n = int(input())
b = {}
c = {}
h = int(n / 2) - 1
for i in range(n):
	a = input().split()
	x = int(a[0])
	if i > h:
		y = a[1]
	else:
		y = '-'
	if x in c:
		c[x] += 1
		b[x] = b[x] + ' ' + y
	else:
		c[x] = 1
		b[x] = y
for i in c:
	k = b[i].split()
	for j in k:
		print(j, end=' ')


a = int(input())
c = []
for i in range(100):
	c.append([])
for i in range(a // 2):
	(x, _) = input().split()
	c[int(x)].append('-')
for i in range(a // 2):
	(x, y) = input().split()
	c[int(x)].append(y.strip())
print(' '.join([item for sublist in c for item in sublist]))


def counting_sort(ar):
	z = [[] for i in range(100)]
	for m in range(len(ar)):
		l = []
		if z[ar[m]] != []:
			l = z[ar[m]]
		l.append(m)
		z[ar[m]] = l
	return z
n = int(input())
ar = []
ars = []
for _ in range(n):
	(x, st) = input().split()
	x = int(x)
	ar.append(x)
	ars.append(st)
z = counting_sort(ar)
for m in range(100):
	if len(z[m]) > 0:
		for i in z[m]:
			if i < n / 2:
				print('-', end=' ')
			else:
				print(ars[i], end=' ')


get_int = lambda : int(input())

def get_tuple(idx):
	items = input().split()
	return [int(items[0])] + [idx] + items[1:]
n = get_int()
items = [get_tuple(i) for i in range(n)]
items = ['-' if t[1] < n // 2 else t[2] for t in sorted(items)]
print(' '.join(items))


def read_data():
	n = int(input())
	ar = dict()
	for idx in range(n):
		tmp = input().split()
		tmp[0] = int(tmp[0])
		if idx < n // 2:
			tmp[1] = '-'
		if tmp[0] in ar:
			ar[tmp[0]].append(tmp[1])
		else:
			ar[tmp[0]] = [tmp[1]]
	return ar
ar = read_data()
string = list()
for key in ar:
	string.extend(ar[key])
print(' '.join(string))


arraySize = int(input())
words = []
for i in range(100):
	words.append([])
for i in range(arraySize):
	line = input().split(' ')
	words[int(line[0])].append('-' if i < arraySize // 2 else line[1])
output = []
for i in range(100):
	output.append(' '.join(words[i]))
print(' '.join(output))


from functools import reduce
n = int(input())
l = []
for i in range(n):
	s = input().split()
	l.append((int(s[0]), s[1]))
c = [[] for i in range(100)]
for (i, s) in l[0:len(l) // 2]:
	c[i].append('-')
for (i, s) in l[len(l) // 2:]:
	c[i].append(s)
print(*reduce(lambda x, xs: x + xs, c, []))


size = int(input())
array = [input().split() for _ in range(size)]
for i in range(len(array) // 2):
	array[i][1] = '-'
element = [[] for _ in range(0, 100)]
for i in array:
	element[int(i[0])].append(i[1])
idx = 0
for i in element:
	for j in i:
		array[idx] = j
		idx += 1
print(' '.join(array))


n = int(input())
arr = []
helper = []
for i in range(n):
	(val, string) = input().rstrip().split()
	arr.append((int(val), string))
	helper.append((int(val), i))
helper.sort()
res = []
for (i, j) in helper:
	if j < n // 2:
		res.append('-')
	else:
		res.append(arr[j][1])
print(*res, sep=' ')


from collections import defaultdict, namedtuple
Entry = namedtuple('Entry', ['key', 'val'])
E = defaultdict(int)
N = int(input())
A = []
for n in range(N):
	(key_str, val) = input().strip().split()
	key = int(key_str)
	if n < N // 2:
		val = '-'
	A.append(Entry(key, val))
	E[key] += 1
offsets = []
acc = 0
for i in range(100):
	offsets.append(acc)
	acc += E[i]
outD = {}
for e in A:
	outD[offsets[e.key]] = e.val
	offsets[e.key] += 1
print(' '.join([outD[k] for k in sorted(outD.keys())]))


def counting_sort(data):
	sorted_data = [0 for i in range(len(data))]
	counts = [0 for i in range(100)]
	prefix_sum_counts = [0 for i in range(100)]
	for x in data:
		counts[x[0]] += 1
	for i in range(0, len(counts)):
		if i == 0:
			prefix_sum_counts[i] = counts[i]
		else:
			prefix_sum_counts[i] = counts[i] + prefix_sum_counts[i - 1]
	for i in range(len(data) - 1, -1, -1):
		sorted_data[prefix_sum_counts[data[i][0]] - 1] = data[i]
		prefix_sum_counts[data[i][0]] -= 1
	return sorted_data

def print_strings(data):
	for x in data:
		print(x[1], end=' ')
	print()
num_lines = int(input())
data = []
for i in range(0, num_lines):
	data.append(input().split(' '))
	data[i][0] = int(data[i][0])
for i in range(0, int(len(data) / 2)):
	data[i][1] = '-'
sorted_data = counting_sort(data)
print_strings(sorted_data)


n = int(input())
f = [0] * 100
a = []
for i in range(n):
	(v, s) = input().split()
	if i < n // 2:
		s = '-'
	v = int(v)
	f[v] += 1
	a.append((v, s))
b = [None] * len(a)
s = 0
for (v, c) in enumerate(f):
	(f[v], s) = (s, f[v] + s)
for (v, s) in a:
	b[f[v]] = s
	f[v] += 1
print(*b)


n = int(input())
(xs, ss) = ([], [])
for _ in range(n):
	(x, s) = input().split()
	xs.append(int(x))
	ss.append(s)
fs = [0 for i in range(100)]
for x in xs:
	fs[x] += 1
fs_cum = [0]
for i in range(len(fs) - 1):
	fs_cum.append(fs[i] + fs_cum[-1])
i_half = n // 2
ys = ['-' for x in xs]
for ((i, x), s) in zip(enumerate(xs), ss):
	if i >= i_half:
		ys[fs_cum[x]] = s
	fs_cum[x] += 1
print(' '.join(ys))


N = int(input())
A = [(int(i), s if n >= N // 2 else '-') for (i, s, n) in (input().split() + [n] for n in range(N))]
print(*(s for (i, s) in sorted(A, key=lambda x: x[0])))


n = int(input())
L = [[] for i in range(100)]
for i in range(n >> 1):
	I = input().split()
	(x, s) = (int(I[0]), '-')
	L[x].append(s)
for i in range(n >> 1, n):
	I = input().split()
	(x, s) = (int(I[0]), I[1])
	L[x].append(s)
for i in range(len(L)):
	for s in L[i]:
		print(s, end=' ')


n = int(input())
inp_idx = [0] * n
inp_str = [''] * n
count = [0] * 100
for i in range(n):
	(idx, s) = input().strip().split()
	inp_idx[i] = int(idx)
	inp_str[i] = s
	count[int(idx)] += 1
out_idx = [0] * 100
for i in range(1, 100):
	out_idx[i] = out_idx[i - 1] + count[i - 1]
out_str = ['-'] * n
for i in range(n):
	if i >= n // 2:
		out_str[out_idx[inp_idx[i]]] = inp_str[i]
	out_idx[inp_idx[i]] += 1
print(' '.join(out_str))


n = int(input())
words = []
result = [''] * n
counts = [0] * 100
positions = [0] * 101
for i in range(n):
	(x, s) = input().split()
	x = int(x)
	counts[x] += 1
	if i < n / 2:
		words.append((x, '-'))
	else:
		words.append((x, s))
positions[-1] = n
for i in range(1, 100):
	positions[i] = positions[i - 1] + counts[i - 1]
for (x, s) in words:
	result[positions[x + 1] - counts[x]] = s
	counts[x] -= 1
print(' '.join(result))


t = int(input())
arr = []
for i in range(t):
	arr.append(input().split(' '))
xRange = 100

def fullCountingSort(arr):
	countArray = [0] * xRange
	for (x, s) in arr:
		countArray[int(x)] += 1
	prev = 0
	for index in range(xRange):
		countArray[index] += prev
		prev = countArray[index]
	answer = ['-'] * len(arr)
	for index in range(len(arr) - 1, len(arr) // 2 - 1, -1):
		countArray[int(arr[index][0])] -= 1
		answer[countArray[int(arr[index][0])]] = arr[index][1]
	return ' '.join(answer)
print(fullCountingSort(arr))


from array import *
n = int(input())
a = n * [0]
b = ['' for i in range(0, 100)]
for i in range(0, int(n // 2)):
	(v, s) = input().split()
	b[int(v)] += '- '
for i in range(int(n // 2 + 1), n + 1):
	(v, s) = input().split()
	b[int(v)] += s + ' '
for i in range(0, 100):
	print(b[i], end='')


from collections import defaultdict
n = int(input())
d = defaultdict(list)
for _ in range(n // 2):
	(x, y) = input().split()
	d[int(x)].append('-')
for _ in range(n // 2):
	(x, y) = input().split()
	d[int(x)].append(y)
print(' '.join([' '.join([i for i in li]) for li in d.values()]))


def count(array):
	count = [0] * 100
	for x in array:
		count[x] += 1
	return count

def startIndexes(counts):
	results = []
	sum = 0
	for num in counts:
		sum += num
		results.append(sum)
	return results
n = int(input())
a = []
words = []
for i in range(n):
	(num, word) = input().split()
	a.append(int(num))
	words.append(word)
counts = count(a)
startIdxs = startIndexes(counts)
startIdxs = [0] + startIdxs
words = ['-'] * int(len(words) / 2) + words[int(len(words) / 2):]
results = [''] * len(words)
for (i, word) in enumerate(words):
	results[startIdxs[a[i]]] = word
	startIdxs[a[i]] += 1
print(' '.join((str(x) for x in results)))


counts = [0 for i in range(100)]
m = int(input().strip())
dict = {}
ar = []
for i in range(m):
	pair = input().strip().split()
	key = int(pair[0])
	value = pair[1]
	ar.append(key)
	if key in dict:
		dict[key].append((i, value))
	else:
		dict[key] = [(i, value)]
for i in ar:
	counts[i] += 1
	j = 0
outstr = ''
for i in counts:
	if i != 0:
		for mm in dict[j]:
			if mm[0] >= m // 2:
				outstr += mm[1] + ' '
			else:
				outstr += '- '
	j += 1
print(outstr[0:len(outstr) - 1])


def getKey(item):
	return int(item.split(' ')[0])

def getMsg(item):
	return item.split(' ')[1]

def countingSort(A):
	countA = [0 for x in range(100)]
	for item in A:
		countA[getKey(item)] += 1
	total = 0
	for i in range(100):
		oldCount = countA[i]
		total += oldCount
		countA[i] = total
	output = ['' for x in range(len(A))]
	i = len(A) - 1
	while i >= 0:
		output[countA[getKey(A[i])] - 1] += getMsg(A[i])
		countA[getKey(A[i])] -= 1
		i -= 1
	return output
n = int(input())
A = []
for i in range(n):
	if i < n / 2:
		A.append(input().split(' ')[0] + ' -')
	else:
		A.append(input())
output = countingSort(A)
print(' '.join(output))


import math
t = int(input())
x = list()
txt = list()
for i in range(t):
	xtxt = input().split()
	x.append(int(xtxt[0]))
	txt.append(xtxt[1])
cnt = [0] * 101
for i in x:
	cnt[i] += 1
y = [cnt[0]]
for j in range(1, 100):
	y = y + [y[-1] + cnt[j]]
y = [0] + y
out = ['-'] * t
for i in range(int(t / 2)):
	y[x[i]] += 1
for i in range(int(t / 2), t):
	out[y[x[i]]] = txt[i]
	y[x[i]] += 1
print(' '.join(out))


ha = [[] for x in range(100)]
n = int(input())
n2 = n // 2
for i in range(n):
	(x, obj) = input().split()
	ha[int(x)].append(obj if i >= n2 else '-')
for (i, j) in enumerate(ha):
	for x in j:
		print(x, end=' ')


n = int(input())
ar = [(int(x), s) for (x, s) in [input().split() for l in range(n)]]
items = [[] for i in range(100)]
for (idx, (x, s)) in enumerate(ar):
	if idx < n / 2:
		items[x].append('-')
	else:
		items[x].append(s)
print(' '.join([' '.join(l) for l in items]))