cgpa-ya-studapa

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.

SAMPLE INPUT
2
3
10 20 30
30 20 10
1 1 1
2
1 2
2 1
1 1

SAMPLE OUTPUT
10 19 28 
1 1

Explanation

In the first case:
Anurag needs atleast 10 spare points to solve even one mission. 
To solve two mission Anurag needs 19 spare points to start with. He can start out by using 10 of the spare points to increase his C. Then he can solve the first challenge and gain 1 spare point. Now after this he has 9 + 1 = 10 spare point by which he can boost C further to make it 20, which will get him the second challenge.
To solve three missions He will need an additional 9 points (a total of 28 points) so that he can boost his C further to 30.

In the second case:
He just needs 1 spare point to solve both the challenges. He can boost C by 1. Then solve the first challenge. Then use the gained spare point for further boosting the C to solve the second challenge.

Source: hackerearth | Difficulty: EASY


Solutions: