Read problem statements in [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Codechef challenges have three divisions. In one challenge, there are $N$ problems in each division, but some problems may be shared among multiple divisions. Each problem is uniquely identified by a *code* — a string containing only uppercase English letters. Each participant can only submit in one of the divisions.

Chef wants to find the number of correct solutions, in total among all $3$ divisions, for each problem. Given a list of $N$ problem codes with the numbers of correct solutions for each problem in each division, find the total number of correct solutions for each problem and sort them in non-decreasing order.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.
$N$ lines follow. For each valid $i$, the $i$-th of these lines contains a string $S_{3,i}$ followed by a space and an integer $C_{3,i}$ — the problem code and the number of correct solutions on the $i$-th problem in the third division.
$N$ more lines follow. For each valid $i$, the $i$-th of these lines contains a string $S_{2,i}$ followed by a space and an integer $C_{2,i}$ — the problem code and the number of correct solutions on the $i$-th problem in the second division.
Finally, $N$ more lines follow. For each valid $i$, the $i$-th of these lines contains a string $S_{1,i}$ followed by a space and an integer $C_{1,i}$ — the problem code and the number of correct solutions on the $i$-th problem in the first division.

------  Output ------
For each test case, let $P$ be the number of distinct problems; you should print $P$ space-separated integers — the number of solutions for each of these problems, sorted in non-decreasing order.

------  Constraints ------
$1 ≤ T ≤ 10$
$1 ≤ N ≤ 2 \cdot 10^{4}$
$1 ≤ |S_{1,i}|, |S_{2,i}|, |S_{3,i}| ≤ 8$ for each valid $i$
$S_{1,i}, S_{2,i}, S_{3,i}$ contain only uppercase English letters for each valid $i$
$1 ≤ C_{1,i}, C_{2,i}, C_{3,i} ≤ 5 \cdot 10^{8}$ for each valid $i$
the problem codes in each division are pairwise distinct, but some problem codes may appear in multiple divisions
the sum of $N$ over all test cases does not exceed $10^{5}$

----- Sample Input 1 ------ 
3
1
A 1
B 2
C 3
2
AA 1
AB 1
AB 1
AC 1
AC 1
AD 1
1
Z 100
Z 100
Z 100
----- Sample Output 1 ------ 
1 2 3
1 1 2 2
300
----- explanation 1 ------ 
Example case 1: There is only $1$ problem in each division and no problems are shared among divisions, so the total number of distinct problems is $3$ and the numbers of solutions are: $1$ for "A", $2$ for "B", $3$ for "C".

Example case 2: There are $2$ problems in each division and each pair of consecutive divisions shares $1$ problem, so the total number of distinct problems is $4$ and the numbers of solutions are: $1$ for "AA", $2$ for "AB", $2$ for "AC", $1$ for "AD". We need to sort them in non-decreasing order, so the final answer is $(1, 1, 2, 2)$.

Example case 3: There is only $1$ problem "Z" in the entire contest, shared among all divisions, and the number of solutions for it is $300$.

Source: codechef | Difficulty: MEDIUM
Tags: Data structures

Implementation


Solutions:
t = int(input())
for dhff in range(t):
	n = int(input())
	d = {}
	for i in range(3 * n):
		(s, num) = input().split()
		newnum = int(num)
		if s in d:
			d[s] += newnum
		else:
			d[s] = newnum
	l = len(d)
	x = list(d.values())
	x.sort()
	for i in x:
		print(i, end=' ')
	print('')


t = int(input())
while t != 0:
	n = int(input())
	hm = {}
	for i in range(0, 3 * n):
		(st, nm) = input().split()
		nm = int(nm)
		if st in hm:
			hm[st] = hm[st] + nm
		else:
			hm[st] = nm
	print_line = ''
	for k in sorted(hm, key=hm.get):
		print_line += str(hm[k]) + ' '
	print(print_line)
	t -= 1


from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	inp = {}
	for i in range(3 * n):
		(code, a) = map(str, input().split())
		if code not in inp:
			inp[code] = int(a)
		else:
			inp[code] += int(a)
	for i in sorted(inp.values()):
		print(i, end=' ')
	print()


t = int(input())
for i in range(0, t):
	ls = int(input())
	d = {}
	for j in range(ls * 3):
		(c, n) = input().split(' ')
		d[c] = d.get(c, 0) + int(n)
	k = d.values()
	n = []
	for m in k:
		n.append(m)
	for m in sorted(n):
		print(m, end=' ')
	print()


for _ in range(int(input())):
	d = {}
	n = int(input())
	for i in range(n * 3):
		(c, s) = map(str, input().split())
		if c not in d:
			d[c] = int(s)
		else:
			d[c] += int(s)
	lis = list(d.values())
	lis.sort()
	print(*lis)


t = int(input())
for i in range(t):
	n = int(input())
	codes = {}
	for j in range(3 * n):
		(code, num) = list(map(str, input().split()))
		if code in codes:
			codes[code] += int(num)
		else:
			codes[code] = int(num)
	solution = sorted(list(codes.values()))
	solution = list(map(str, solution))
	print(' '.join(solution))


for _ in range(int(input())):
	n = int(input())
	d = {}
	for i in range(3 * n):
		(a, b) = map(str, input().split())
		b = int(b)
		if a not in d:
			d[a] = b
		else:
			d[a] += b
	l = list(d.values())
	l.sort()
	print(*l)


for t in range(int(input())):
	n = int(input())
	d = {}
	for i in range(3 * n):
		a = list(input().split())
		d[a[0]] = d.get(a[0], 0) + int(a[1])
	v = list(d.values())
	v.sort()
	for i in v:
		print(i, end=' ')
	print()


t = int(input())
output = ''
for i in range(t):
	n = int(input())
	dict = {}
	for k in range(3 * n):
		string_list = input().split(' ')
		(code, number) = (string_list[0], int(string_list[1]))
		if code not in dict:
			dict[code] = number
		else:
			dict[code] = dict.get(code) + number
	output += f"{' '.join(map(str, sorted(dict.values())))}\n"
print(output)


for _ in range(int(input())):
	n = int(input())
	x = []
	d = {}
	for i in range(3 * n):
		s = [str(i) for i in input().split()]
		x.append(s)
	for i in range(len(x)):
		if x[i][0] not in d:
			d[x[i][0]] = int(x[i][1])
		else:
			d[x[i][0]] += int(x[i][1])
	k = list(d.values())
	k.sort()
	print(*k)


n_cases = int(input())
for _ in range(n_cases):
	n_probs_per_div = int(input())
	ctr = {}
	for _ignore in range(3 * n_probs_per_div):
		(code, score_st) = input().split()
		ctr[code] = ctr.get(code, 0) + int(score_st)
	print(' '.join((str(x) for x in sorted(ctr.values()))))


for _ in range(int(input())):
	N = int(input())
	dc = {}
	for i in range(3 * N):
		(s, c) = input().split()
		if s in dc:
			dc[s] = dc[s] + int(c)
		else:
			dc[s] = int(c)
	for i in sorted(dc.values()):
		print(i, end=' ')
	print('\n')


for _ in range(int(input())):
	n = int(input())
	dic = {}
	for i in range(n * 3):
		(a, b) = input().split(' ')
		if a in dic:
			dic[a] += int(b)
		else:
			dic[a] = int(b)
	l = list(dic.values())
	l.sort()
	print(*l)


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	d = defaultdict(int)
	for i in range(3 * n):
		(s1, s2) = map(str, input().split())
		d[s1] += int(s2)
	v = list(d.values())
	v.sort()
	print(*v)


for _ in range(int(input())):
	questions = {}
	for num in range(int(input()) * 3):
		lift = list(input().split())
		lift[1] = int(lift[1])
		if lift[0] not in questions:
			questions[lift[0]] = lift[1]
		else:
			questions[lift[0]] += lift[1]
	new_list = sorted(questions.values())
	to_print = ''
	for thing in new_list:
		to_print = to_print + str(thing) + ' '
	print(to_print)


for _ in range(int(input())):
	d = {}
	for i in range(3 * int(input())):
		(code, sub) = input().split()
		sub = int(sub)
		if code in d:
			d[code] += sub
		else:
			d[code] = sub
	values = list(d.values())
	values.sort()
	print(*values)


n = int(input())
for i in range(1, n + 1):
	k = int(input())
	dict = {}
	for j in range(k * 3):
		(x, y) = input().split()
		try:
			dict[x] += int(y)
		except:
			dict[x] = int(y)
	z = list(dict.values())
	z.sort()
	for j in z:
		print(j, end=' ')
	print()


num = int(input())
for i in range(num):
	n = int(input())
	case = []
	for j in range(n * 3):
		c = input().split()
		case.append(c)
	count = {}
	for prob in case:
		count[prob[0]] = 0
	for prob in case:
		count[prob[0]] += int(prob[1])
	arr = count.values()
	arr = sorted(arr)
	print(*arr)


n = int(input())
for i in range(n):
	x = int(input())
	d = {}
	for ii in range(x * 3):
		(xx, xxx) = input().split()
		xxx = int(xxx)
		if xx in d:
			d[xx] += xxx
		else:
			d[xx] = xxx
	print(*sorted([d[i] for i in d]))


for i in range(int(input())):
	n = int(input())
	d = {}
	for j in range(n * 3):
		l = input().split()
		l[1] = int(l[1])
		if l[0] not in d:
			d[l[0]] = l[1]
		else:
			d[l[0]] += l[1]
	for k in sorted(d.values()):
		print(f'{k} ', end='')
	print()


t = int(input())
for i in range(t):
	n = int(input())
	n = 3 * n
	dictQuest = {}
	for i in range(n):
		(q, c) = [i for i in input().split()]
		if q in dictQuest.keys():
			dictQuest[q] = dictQuest[q] + int(c)
		else:
			dictQuest[q] = int(c)
	ans = list(dictQuest.values())
	for i in sorted(ans):
		print(i, end=' ')
	print()


t = int(input())
for i in range(t):
	n = int(input())
	d = {}
	for j in range(3 * n):
		(s, c) = map(str, input().split())
		if s in d:
			d[s] += int(c)
		else:
			d[s] = int(c)
	l = []
	for j in d:
		l += [d[j]]
	l.sort()
	print(*l)


for t in range(int(input())):
	n = int(input())
	l = {}
	for j in range(n * 3):
		(x, y) = input().split()
		y = int(y)
		if x not in l:
			l[x] = y
		else:
			l[x] += y
	for i in sorted(l.values()):
		print(i, end=' ')
	print()


n = int(input())
for i in range(n):
	n1 = int(input())
	d = {}
	for i in range(n1 * 3):
		(k, y) = input().split()
		if k not in d:
			d[k] = int(y)
		else:
			d[k] += int(y)
	for i in sorted(d.values()):
		print(i, end=' ')
	print()


for row_number in range(0, int(input())):
	number_of_problems = int(input()) * 3
	problems_to_correct_solutions_dict = dict()
	for _ in range(0, number_of_problems):
		(problem_name, correct_solutions_string) = input().split(' ')
		correct_solutions = int(correct_solutions_string)
		if problem_name in problems_to_correct_solutions_dict:
			correct_solutions += problems_to_correct_solutions_dict[problem_name]
		problems_to_correct_solutions_dict[problem_name] = correct_solutions
	sortedList = sorted(problems_to_correct_solutions_dict.values())
	print(*sortedList)


T = int(input())
while T > 0:
	N = int(input())
	lt = []
	dic = {}
	for i in range(3 * N):
		(s, c) = input().split()
		if s not in dic:
			dic[s] = int(c)
		else:
			dic[s] += int(c)
	for i in dic.values():
		lt.append(i)
	lt.sort()
	for i in lt:
		print(i, end=' ')
	print()
	T = T - 1


for _ in range(int(input())):
	n = int(input())
	d = {}
	for i in range(3 * n):
		(a, b) = map(str, input().split())
		if a in d:
			d[a] += int(b)
		else:
			d[a] = int(b)
	l = []
	for i in d:
		l.append(d[i])
	l.sort()
	print(*l)


for _ in range(int(input())):
	n = int(input())
	num_solutions = dict()
	for _ in range(3 * n):
		data = input().split()
		if data[0] not in num_solutions:
			num_solutions[data[0]] = 0
		num_solutions[data[0]] += int(data[1])
	output = [str(x) for x in sorted(list(num_solutions.values()))]
	print(' '.join(output))


for x in range(int(input())):
	n = int(input())
	d = {}
	for i in range(3 * n):
		(code, correct) = input().rstrip().split()
		correct = int(correct)
		d[code] = d[code] + correct if code in d else correct
	print(' '.join(list(map(str, sorted(d.values())))))


t = int(input())
for i in range(t):
	n = int(input())
	a = {}
	for j in range(3 * n):
		l = list(input().split())
		(b, c) = (l[0], int(l[1]))
		if b not in a:
			a[b] = c
		else:
			a[b] += c
	g = list(a.values())
	g.sort()
	for j in g:
		print(j, end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	a = {}
	for i in range(3 * n):
		(p, q) = map(str, input().split())
		q = int(q)
		if p not in a.keys():
			a[p] = q
		else:
			a[p] += q
	x = list(a.values())
	x.sort()
	for i in range(len(x)):
		print(x[i], end=' ')
	print(' ')


for _ in range(int(input())):
	N = int(input())
	B = {}
	for i in range(3 * N):
		(c, ch) = input().split(' ')
		B[c] = B.get(c, 0) + int(ch)
	for t in sorted(list(B.values())):
		print(t, end=' ')
	print('\n')


for _ in range(int(input())):
	N = int(input())
	d = {}
	X = []
	Y = []
	for i in range(3 * N):
		(x, y) = map(str, input().split())
		X.append(x)
		Y.append(int(y))
	for i in X:
		d[i] = 0
	for (i, j) in zip(X, Y):
		d[i] += j
	xxx = list(d.values())
	xxx.sort()
	xx = ''
	for i in xxx:
		xx += str(i) + ' '
	print(xx[:-1])


for _ in range(int(input())):
	n = int(input())
	problem_dict = {}
	for _ in range(3):
		for _ in range(n):
			(code, sub) = input().split(' ')
			sub = int(sub)
			if code in problem_dict.keys():
				problem_dict[code] += sub
			else:
				problem_dict[code] = sub
	ans = list(problem_dict.values())
	ans.sort()
	print(' '.join(map(str, ans)))


a = input()
for _ in range(int(a)):
	b = {}
	n = int(input())
	for i in range(3 * n):
		(c, ch) = input().split(' ')
		b[c] = b.get(c, 0) + int(ch)
	for t in sorted(list(b.values())):
		print(t, end=' ')
	print('\n')


test_cases = input()
for _ in range(int(test_cases)):
	ques_obj = {}
	n = int(input())
	for i in range(3 * n):
		(question, choice) = input().split(' ')
		ques_obj[question] = ques_obj.get(question, 0) + int(choice)
	for val in sorted(list(ques_obj.values())):
		print(val, end=' ')
	print('\n')


t = int(input())
for i in range(t):
	n = int(input())
	d = {}
	for j in range(3 * n):
		(s, k) = input().split()
		k = int(k)
		if s in d:
			d[s] += k
		else:
			d[s] = k
	p = list(d.values())
	p.sort()
	for i in p:
		print(i, end=' ')
	print()


for t in range(int(input())):
	n = int(input())
	(s1, s2, s3, c1, c2, c3) = ([], [], [], [], [], [])
	for i in range(n):
		x = input().split()
		s3.append(x[0])
		c3.append(int(x[1]))
	for i in range(n):
		x = input().split()
		s2.append(x[0])
		c2.append(int(x[1]))
	for i in range(n):
		x = input().split()
		s1.append(x[0])
		c1.append(int(x[1]))
	d = {}
	for i in range(n):
		if s3[i] in d.keys():
			d[s3[i]] += c3[i]
		else:
			d[s3[i]] = c3[i]
	for i in range(n):
		if s2[i] in d.keys():
			d[s2[i]] += c2[i]
		else:
			d[s2[i]] = c2[i]
	for i in range(n):
		if s1[i] in d.keys():
			d[s1[i]] += c1[i]
		else:
			d[s1[i]] = c1[i]
	ans = list(d.values())
	ans.sort()
	for i in ans:
		print(i, end=' ')
	print()


for t in range(int(input())):
	n = int(input())
	dictmain = {}
	for i in range(3 * n):
		a = input().split()
		if a[0] in dictmain:
			dictmain[a[0]] += int(a[1])
		else:
			dictmain[a[0]] = int(a[1])
	a = list(dictmain.values())
	a.sort()
	for i in range(len(a) - 1):
		print(a[i], end=' ')
	print(a[-1])


for _ in range(int(input())):
	n = int(input())
	d = {}
	for i in range(3 * n):
		(a, b) = input().split()
		if a in d:
			d[a] += int(b)
		else:
			d[a] = int(b)
	d = sorted(d.values())
	for i in d:
		print(i, end=' ')
	print()


t = int(input())
for _ in range(t):
	n = int(input())
	solutions = {}
	for i in range(3):
		for j in range(n):
			(code, count) = input().split()
			count = int(count)
			solutions[code] = solutions.get(code, 0) + count
	solutions = {k: v for (k, v) in sorted(solutions.items(), key=lambda item: item[1])}
	for code in solutions:
		print(solutions[code], end=' ')
	print()


from collections import defaultdict
test_cases = int(input())
for _ in range(test_cases):
	problems = int(input())
	dictionary = defaultdict(int)
	for _ in range(problems * 3):
		user_input = input().split()
		dictionary[user_input[0]] += int(user_input[1])
	arr = [value for (_, value) in dictionary.items()]
	arr.sort()
	for elem in arr:
		print(elem, end=' ')
	print()


dic = {}
for _ in range(int(input())):
	dic = {}
	n = int(input())
	for i in range(n * 3):
		l = input().split()
		if l[0] in dic:
			dic[l[0]] += int(l[1])
		else:
			dic[l[0]] = int(l[1])
	lst = []
	for i in dic:
		lst.append(dic[i])
	for i in sorted(lst):
		print(i, end=' ')
	print()


t = int(input())
for i in range(0, t):
	n = int(input())
	d = {}
	for i in range(0, 3 * n):
		a = input().split()
		(a, b) = a
		b = int(b)
		if a in d:
			d[a] += b
		else:
			d[a] = b
	l = []
	for i in d:
		l += [d[i]]
	l.sort()
	for i in l:
		print(i, end=' ')
	print()


for i in range(int(input())):
	N = int(input())
	mydict = {}
	string = ''
	for i in range(3):
		for i in range(N):
			problem = str(input())
			stringWithChar = ''
			stringWithInt = ''
			for _ in problem:
				if _.isdigit() == True:
					stringWithInt += str(_)
				else:
					stringWithChar += str(_)
			if stringWithChar in mydict:
				mydict[stringWithChar] += int(stringWithInt)
			else:
				mydict[stringWithChar] = int(stringWithInt)
	sortedDict = {k: v for (k, v) in sorted(mydict.items(), key=lambda item: item[1])}
	for i in sortedDict.values():
		string = string + ' ' + str(i)
	print(string)


def solve(codes, corrSol, n):
	mp = {}
	for i in range(n * 3):
		if codes[i] not in mp:
			mp[codes[i]] = corrSol[i]
		else:
			mp[codes[i]] += corrSol[i]
	res = sorted(mp.values())
	return res
for _ in range(int(input())):
	n = int(input())
	codes = []
	corrSol = []
	for i in range(n * 3):
		(v1, v2) = input().split()
		codes.append(v1)
		corrSol.append(int(v2))
	print(*solve(codes, corrSol, n))


for _ in range(int(input())):
	d = {}
	for i in range(3 * int(input())):
		p = input().split()
		(p, s) = p
		s = int(s)
		if p in d:
			d[p] += s
		else:
			d[p] = s
	l = []
	for i in d:
		l += [d[i]]
	l.sort()
	for i in l:
		print(i, end=' ')
	print()


testCases = int(input())
for tc in range(testCases):
	n = int(input())
	submission_map = {}
	for i in range(3 * n):
		(prob_code, submissions) = map(str, input().split())
		if prob_code in submission_map:
			submission_map[prob_code] += int(submissions)
		else:
			submission_map[prob_code] = int(submissions)
	submission_map = dict(sorted(submission_map.items(), key=lambda x: x[1]))
	for key in submission_map:
		print(submission_map[key], end=' ')
	print()


for ii in range(int(input())):
	No = int(input())
	Dict = {}
	for i in range(No * 3):
		List = input().split()
		if List[0] in Dict:
			Dict[List[0]] += int(List[1])
		else:
			Dict[List[0]] = int(List[1])
	for val in sorted(Dict.values()):
		print(val, end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	dict = {}
	for i in range(3 * n):
		x = input().split(' ')
		if x[0] not in dict.keys():
			dict[x[0]] = int(x[1])
		else:
			v = dict[x[0]]
			dict[x[0]] = v + int(x[1])
	dl = list(dict.values())
	dl.sort()
	print(*dl)


for _ in range(int(input())):
	n = 3 * int(input())
	d = {}
	for _ in range(n):
		(problem, count) = input().split()
		count = int(count)
		if problem not in d:
			d[problem] = count
		else:
			d[problem] += count
	strvals = list(map(str, sorted(list(d.values()))))
	print(' '.join(strvals))


import sys
import math
import heapq
from collections import defaultdict as dd
from collections import OrderedDict as od
from collections import deque
from itertools import permutations as pp
from itertools import combinations as cc
from sys import stdin
from functools import cmp_to_key
from functools import lru_cache
from bisect import bisect_left as bs_l
from bisect import bisect_right as bs_r
input = sys.stdin.readline
mod = 10 ** 9 + 7
sys.setrecursionlimit(10 ** 5)
T = int(input())
for _ in range(T):
	n = int(input())
	d = dd(int)
	for i in range(3 * n):
		(nm, c) = input().strip().split(' ')
		d[nm] += int(c)
	l = []
	for i in d:
		l.append(d[i])
	l.sort()
	print(*l)


tc = int(input())
while tc > 0:
	tc = tc - 1
	dic = {}
	shared_problems = int(input()) * 3
	while shared_problems > 0:
		shared_problems = shared_problems - 1
		div = input().split(' ')
		if div[0] in dic.keys():
			val = dic[div[0]]
			dic[div[0]] = val + int(div[1])
		else:
			dic[div[0]] = int(div[1])
	mylist = list(dic.values())
	mylist.sort()
	print(*mylist)


t = int(input())
for i in range(t):
	d = {}
	n = int(input())
	for i in range(3):
		for j in range(n):
			k = list(input().split())
			if k[0] not in d.keys():
				d[k[0]] = int(k[1])
			else:
				d[k[0]] += int(k[1])
	l = list(d.values())
	l.sort()
	print(*l)


for _ in range(int(input())):
	n = int(input())
	f = lambda : map(str, input().split())
	h = {}
	for j in range(3):
		for i in range(n):
			(a, b) = f()
			b = int(b)
			if a in h:
				h[a] += b
			else:
				h[a] = b
	sorredh = sorted(h.items(), key=lambda x: x[1])
	result = []
	for i in range(len(sorredh)):
		result.append(sorredh[i][1])
	print(*result, sep=' ')


for testcases in range(int(input())):
	n = int(input()) * 3
	d = {}
	for i in range(n):
		(a, b) = map(str, input().split())
		if a in d:
			d[a] += int(b)
		else:
			d[a] = int(b)
	l = list((int(x) for x in d.values()))
	l.sort()
	print(*l)


t = int(input())
for test in range(t):
	N = int(input())
	submissionsDictionary = {}
	for submission in range(N * 3):
		(key, number) = input().split(' ')
		number = int(number)
		if key in submissionsDictionary:
			submissionsDictionary[key] += number
		else:
			submissionsDictionary.update({key: number})
	submissionsList = []
	for submission in submissionsDictionary:
		submissionsList.append(submissionsDictionary[submission])
	submissionsList.sort()
	submissionsString = ''
	for submission in submissionsList:
		submissionsString += f'{submission} '
	print(submissionsString)


for _ in range(int(input())):
	N = int(input())
	submissions = {}
	divisions = []
	i = 0
	while i < 3:
		for _ in range(N):
			(code, number) = input().split()
			number = int(number)
			dic = {code: number}
			divisions.append(dic)
			submissions[code] = 0
		i += 1
	for dic in divisions:
		for key in dic:
			submissions[key] += dic[key]
	divisions.clear()
	for key in submissions:
		divisions.append(submissions[key])
	divisions.sort()
	for successful in divisions:
		print(successful, end=' ')
	print()


T = int(input())
for iter in range(T):
	N = int(input())
	storage = {}
	for x in range(N * 3):
		(codeTag, solutions) = input().split()
		if codeTag not in storage.keys():
			storage[codeTag] = int(solutions)
		else:
			storage[codeTag] += int(solutions)
	freq = list(storage.values())
	freq.sort()
	print(' '.join(map(str, freq)))


def solve():
	d = {}
	N = int(input())
	for i in range(3 * N):
		(s, c) = input().split()
		ci = int(c)
		if s in d:
			d[s] += ci
		else:
			d[s] = ci
	a = list(d.values())
	a.sort()
	print(*a)
T = int(input())
for _ in range(T):
	solve()


for _ in range(int(input())):
	n = int(input())
	d = {}
	for _ in range(n * 3):
		(a, b) = input().split()
		if a in d:
			d[a] += int(b)
		else:
			d[a] = int(b)
	val = d.values()
	print(' '.join(list(map(str, sorted(val)))))


n_divs = 3
t = int(input())
for i in range(t):
	n = int(input())
	p = dict()
	for j in range(n_divs):
		for k in range(n):
			(s, c) = input().split()
			c = int(c)
			if s in p:
				p[s] += c
			else:
				p[s] = c
	for c in sorted(p.values()):
		print(c, end=' ')
	print()


tests = int(input())
for i in range(tests):
	num = int(input())
	unique_dict = {}
	for j in range(num * 3):
		(problem, solved) = input().split()
		if problem in unique_dict:
			unique_dict[problem] += int(solved)
		else:
			unique_dict[problem] = int(solved)
	ans = sorted(list(unique_dict.values()))
	print(*ans)


for _ in range(int(input())):
	code_dict = {}
	n = int(input())
	for i in range(3):
		for j in range(n):
			(s, c) = map(str, input().split())
			if s in code_dict:
				code_dict[s] += int(c)
			else:
				code_dict[s] = int(c)
	values = list(code_dict.values())
	values.sort()
	for i in values:
		print(i, end=' ')
	print()


t = int(input())
while t:
	n = int(input())
	d = {}
	while n:
		temp = []
		(one, key1) = input().split()
		(two, key2) = input().split()
		(three, key3) = input().split()
		temp.append(int(key1))
		temp.append(int(key2))
		temp.append(int(key3))
		temp1 = []
		temp1.append(one)
		temp1.append(two)
		temp1.append(three)
		for i in range(3):
			if temp1[i] in d:
				d[temp1[i]] += temp[i]
			else:
				d[temp1[i]] = temp[i]
		n -= 1
	x = list(d.values())
	x.sort()
	print(*x, sep=' ')
	t -= 1


for t in range(int(input())):
	d = {}
	for t in range(int(input()) * 3):
		(s, n) = input().split(' ')
		n = int(n)
		if s in d:
			d[s] += n
		else:
			d[s] = n
	l = list(d.values())
	l.sort()
	for a in l:
		print(a, end=' ')
	print()


for _ in range(int(input())):
	N = int(input())
	problems = {}
	total_lines = 3 * N
	for problem in range(total_lines):
		(prob_code, crt_solutions) = input().split(' ')
		crt_solutions = int(crt_solutions)
		if prob_code in problems:
			problems[prob_code] += crt_solutions
		else:
			problems[prob_code] = crt_solutions
	list_crt_sol = list(problems.values())
	list_crt_sol.sort()
	print(*list_crt_sol, sep=' ')


for _ in range(int(input())):
	p = int(input())
	d = {}
	for i in range(0, 3 * p):
		s = input().split()
		if s[0] not in d:
			d[s[0]] = int(s[1])
		else:
			d[s[0]] += int(s[1])
	l = list(d.values())
	l.sort()
	for i in l:
		print(i, end=' ')
	print()


t = int(input())
for _ in range(t):
	npindiv = int(input())
	dat = dict()
	for __ in range(npindiv * 3):
		cur = list(map(str, input().split(' ')))
		ch = cur[0]
		n = int(cur[1])
		if ch in dat.keys():
			dat[ch] += n
		else:
			dat[ch] = n
	l = []
	for i in dat.keys():
		l.append(dat[i])
	l = sorted(l)
	print(*l, sep=' ')


for _ in range(int(input())):
	n = int(input())
	dic = {}
	for i in range(3 * n):
		(s, k) = input().split()
		if s not in dic:
			dic[s] = int(k)
		else:
			dic[s] += int(k)
	u = list(dic.values())
	u.sort()
	print(*u)


t = int(input())
for i in range(t):
	n = int(input())
	d1 = {}
	d2 = {}
	d3 = {}
	keys = []
	for j in range(n):
		x = input().split(' ')
		d3[x[0]] = int(x[1])
		keys.append(x[0])
	for j in range(n):
		x = input().split(' ')
		d2[x[0]] = int(x[1])
		keys.append(x[0])
	for j in range(n):
		x = input().split(' ')
		d1[x[0]] = int(x[1])
		keys.append(x[0])
	unq_keys = list(set(keys))
	ans = []
	for j in unq_keys:
		c = 0
		if j in d1.keys():
			c += d1[j]
		if j in d2.keys():
			c += d2[j]
		if j in d3.keys():
			c += d3[j]
		ans.append(c)
	ans.sort()
	for m in ans:
		print(m, end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	d = {}
	for i in range(3 * n):
		(x, y) = input().split()
		if x not in d:
			d.update({x: int(y)})
		else:
			d[x] += int(y)
	print(*sorted(d.values()))


import sys
for i in range(int(input())):
	n = int(input())
	a = dict()
	for x in range(3 * n):
		(s, c) = sys.stdin.readline().split()
		c = int(c)
		if s not in a:
			a[s] = c
		else:
			a[s] += c
	a = list(a.values())
	print(*sorted(a))


for i in range(int(input())):
	n = int(input())
	a = dict()
	for x in range(3 * n):
		(s, c) = input().split()
		c = int(c)
		if s not in a:
			a[s] = c
		else:
			a[s] += c
	a = list(a.values())
	print(*sorted(a))