Anurag is a good boy. He studies at IIT Kharagpur, where a person's capabilities are measured on two scales

• CGPA : academic performance, denoted by C
• Studapa: coolness/popularity, denoted by S

There are N challenges that one can face at IIT Kharagpur. To pass a challenge i one needs to have C >= ReqC[i] OR S >= ReqS[i]. Completing a challenge does not decrease the capabilities. In fact, P[i] spare points are awarded on completion of challenge i . Spare points can be used to boost the capabilities in any manner.
For example if Anurag wants to use 5 spare points then he can use it to increase his his C by 0 and S by 5 or, C by 1 and S by 4 or, C by 2 and S by 3, and so on. Even though spare points can be used at any time, once used, the spare points cannot be gained back.

Initially Anurag has C = 0 and S = 0. He has an image to keep and he wants to know before hand how many spare points will enable him to win how many challenges.

Constraints

• 1 ≤ T ≤ 20 (Number of test cases)
• 1 ≤ N ≤ 100
• 0 ≤ ReqC[i] ≤10^9
• 0 ≤ ReqS[i] ≤ 10^9
• 0 ≤ P[i] ≤ 10^9

Input

The first line contains T, the number of test cases. Then T test cases follow.

The fist line of each test case contains N. The next line contains N integers of the array ReqC. The next line contains N integers of the array ReqS. The next line contains N integers of the array P.

Output

Print T lines, one for each test case. For each test case print N space separated integers. The first integer represents the minimum number of spare points needed to complete 1 challenge, the second integer represents the minimum number of spare points needed to complete 2 challenges, and so on.