Read problems statements in Mandarin Chinese and Russian as well.

Crueland is a dangerous region following ancient traditions. Every day, there are confrontations among local rulers, and thus many civilians are forced to be refugees. The only recognized way of resolving issues in Crueland is by means of physical power.

King George is thought to be one of the most reasonable and careful rulers in Crueland. As a reasonable ruler, he understands that the best defense is a good offense. Therefore, he decided to conquer some castles and lands to frighten his enemies.

There are N castles that can be conquered by George. As a careful ruler, he won't let his people die without a strong reason. After careful solitary consideration, he has decided to conquer exactly K castles during the next K days, an aim he plans to achieve by conquering one castle every day for the next K days.

As reported by King George's spies, A_i + (j - 1) × B_i enemy knights will be protecting the i^th castle during thej^th day. When attacking a castle, if the King sends as many knights as those defending it, it's sufficient to be conquer that castle. Another requirement is that one knight cannot be sent to conquer two different castles.

Now, you are the Hand of the King. Though caring about the King is your duty, you know that he is a tyrant and you want people to learn the truth about him. Thus, you want to sabotage George's military campaign: maximize the total number of knights used during all the conquests. In this way, his subjects will learn that he doesn't care about them too much. As you are the king's trusted advisor, you can choose a set of K castles, that the king should conquer. George trusts you enough, so you are assured that he will conquer exactly the set of castles you chose. After you provide a set of castles, George will choose the order in which he will conquer them. You can assume that George always chooses the order which minimizes the total number of knights used during all the conquests.

Your task is to find the maximum possible total number of knights that can be used during the campaign and reached by delegating a set of K castles to conquer. Also, you are not sure about the value of K, so you should find the optimal answer for each K = 1, 2, ... , N.

Input

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.

The first line of a test case description contains a single integer N.

The second line of the description contains N integers, where the i^th denotes A_i.

The third line of the description contains N integers, where the i^th denotes B_i.

Output

For each test case, output a single line containing N integers: the maximal possible total number of knights used during all the campaign for each K = 1, 2, ... , N.

Constraints

• 1 ≤ T ≤ 10
• 1 ≤ N ≤ 5000
• 0 ≤ A_i, B_i ≤ 10⁹

Example

Input:
2
4
3 1 1 5
4 5 3 4
5
4 6 4 4 3
9 6 7 9 8

Output:
5 12 21 31
6 17 36 61 91

The language was a quite complicated one but it was sufficient to maximise the minimum amount of soldiers required to 

conquer the fort each day. Now going by the greedy approach obviously greedy as from the kings side for each day we must try to send maximum B[i]s in the first as it increases by a factor of (j-1) but A[i] is constant. So we sort the array according to decreasing value of B[i] and the go for a DP appraoch.

EXPLANATION:

================ 
First of all let's observe the strategy of king. He is given a set of K castles and two arrays A1,A2,...,AK and B1,B2,...,BK are given. For conquering castle i on day j he has to send Ai+(j−1)∗Bi knights. His aim is to decide such an ordering of conquering such that total number of knights required is minimised.

Now, he has to pay Ai for each castle i independent of which day he conqueres it on. So, the ordering depends only onBi. If we think of a greedy approach we should first conquer those castles with highest Bi since, as the day number increases (j−1)∗Bi will also increase. So, this is the the strategy of king: Conquer all K castles in non-increasing order of Bi.

Now, moving onto solving the problem. Let's solve for a particular K. So, we have to choose K castles out of N such that using king's approach maximum number of knights are used. Now, a greedy approach which selects only of basis ofAi or Bi would be certainly wrong. We should, by now, be thinking on terms of dynamic programming.

Now, if you remember subset sum DP, we kept our states as (i,j) denoting that we are solving for first i elements and we need to form a sum j. If we try to think on similar terms here, we should keep our states as (i,j) denoting that we are solving for first i elements and we need to select j castles to maximise knights required according to king's strategy. Now, we have to make a decision that either we select ith castle or not. If we select it, do we know what its going to contribute i.e. how many knights are going to be required? For that we should know on which day king will conquer this castle. Now, here is the interesting part: if we sort the initial arrays in decreasing order of Bi, then we'll be sure that according to king's strategy ith castle will be conquered on last day because all other castles that will be selected will have Bj less than Bi.

So, we first sort arrays A and B in decreasing order of B while preserving the mutual connectedness of Ai and Bi. After that, we define f(i,j) as maximum number of knights required for king to conquer a subset of j castles from first i castles.

Recurrences can be define easily as:
f(i, j) = max(
        \\don't select i'th castle
        f(i - 1, j)

        \\select i'th castle, add the cost
        f(i - 1, j - 1) + (A[i] + (j - 1)*B[i])     
    )


Realising base cases is very easy. So, we calculate f(N−1,i) for all i=1,2,...,N and print them.





#include<iostream>

#include<bits/stdc++.h>

using namespace std;

#define ll long long int

#define mp make_pair

#define pb push_back

#define ff first

#define ss second

ll comp(pair<ll,ll> &a, pair<ll,ll> &b)

{

     if(a.second>b.second)

     return 1;

     else if(a.second==b.second)

     {

        return (a.first<b.first);

        

  }

  return 0;

}

ll a[5010];

ll b[5010];

ll dp[5010][5010];

int main()

{

 int t;

 cin>>t;

 while(t--)

 {

    int n;

    scanf("%d",&n);

    for(int i=1;i<=n;i++)

    {

        scanf("%lld",&a[i]);

    }

    vector<pair<ll,ll> > v;

    for(int i=1;i<=n;i++)

    {

       scanf("%lld",&b[i]);

       v.pb(mp(a[i],b[i]));

    }

    sort(v.begin(),v.end(),comp);

    memset(dp,0,sizeof(dp));

    for(int i=1;i<=n;i++)

    {

       for(int j=1;j<=i;j++)

       {

          dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+v[i-1].ff+(j-1)*v[i-1].ss);  

     }

    }

    for(int i=1;i<=n;i++)

    {

       printf("%lld ",dp[n][i]);

    }

    cout<<endl;

 }

 return 0;

}