Total Correct Submissions Codechef Solution

by

Total Correct Submissions Solution Problem Code: TOTCRT

Codechef challenges have three divisions. In one challenge, there are NN 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 33 divisions, for each problem. Given a list of NN 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 TT denoting the number of test cases. The description of TT test cases follows.
  • The first line of each test case contains a single integer NN.
  • NN lines follow. For each valid ii, the ii-th of these lines contains a string S3,iS3,i followed by a space and an integer C3,iC3,i — the problem code and the number of correct solutions on the ii-th problem in the third division.
  • NN more lines follow. For each valid ii, the ii-th of these lines contains a string S2,iS2,i followed by a space and an integer C2,iC2,i — the problem code and the number of correct solutions on the ii-th problem in the second division.
  • Finally, NN more lines follow. For each valid ii, the ii-th of these lines contains a string S1,iS1,i followed by a space and an integer C1,iC1,i — the problem code and the number of correct solutions on the ii-th problem in the first division.

Output

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

Constraints

  • 1≤T≤101≤T≤10
  • 1≤N≤2⋅1041≤N≤2⋅104
  • 1≤|S1,i|,|S2,i|,|S3,i|≤81≤|S1,i|,|S2,i|,|S3,i|≤8 for each valid ii
  • S1,i,S2,i,S3,iS1,i,S2,i,S3,i contain only uppercase English letters for each valid ii
  • 1≤C1,i,C2,i,C3,i≤5⋅1081≤C1,i,C2,i,C3,i≤5⋅108 for each valid ii
  • the problem codes in each division are pairwise distinct, but some problem codes may appear in multiple divisions
  • the sum of NN over all test cases does not exceed 105105

Example Input

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

Example Output

1 2 3
1 1 2 2
300

Explanation

Example case 1: There is only 11 problem in each division and no problems are shared among divisions, so the total number of distinct problems is 33 and the numbers of solutions are: 11 for “A”, 22 for “B”, 33 for “C”.

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

Example case 3: There is only 11 problem “Z” in the entire contest, shared among all divisions, and the number of solutions for it is 300300.

Weekly Contest 247

Biweekly Contest 55

June Long Challenge 2021 Solutions

March Long Challenge 2021 Solutions

April Long Challenge 2021 Solutions

Codechef Long Challenge Solutions

February Long Challenge 2021

January Long Challenge 2021

November Challenge 2020 SOLUTION CodeChef

October Lunchtime 2020 CodeChef SOLUTIONS

Related :

Related :

Leave a Comment

2 × 5 =