TI10 and ICPC World Finals 2020, which will be held earlier? Take a bet!
The International(TI) is the biggest and most prestigious event of Dota2 and is commonly held annually in August. The Dota2 teams should try to earn points to be eligible to compete in TI. There are two ways of earning points, first is by competing in the regional contests, second is by competing in the tournaments, where all teams are gathered to compete together and earn points according to their rank in the tournament. A team's final score is the sum of scores from both the regional contests and tournaments.
Now that the regional contests have finished, there are n teams taking part, and the ith team has earned ai points from the regional contests. Also, the team that gets the ith rank in the tournament can gain bi points.
cyz is a huge fan of Dota2. So before the tournament starts, he will predict the final rank of all teams. cyz wants to know, for each team, what's its best possible rank and its worst possible rank after the tournament finishes.
If a team has a final score equal to x, its rank is defined as one plus the number of teams with a strict higher score than it. For example, if the final score of four teams are 700,500,500,300 respectively, then their final ranks are 1,2,2,4, respectively.
Input
The first line contains a number T(1≤T≤20), denoting the number of test cases.
The first line of each test case contains one number n(1≤n≤5000), denoting the number of different teams that participate in the regional contests and tournaments.
The next line contains n integers a1,a2,…,an(0≤ai≤109), denoting the points of each team before the tournament starts.
Then follows one line containing n integers b1,b2,…,bn(0≤bn≤bn−1≤...≤b1≤109), where bi denotes the number of points a team would get if ranking ith in the tournament.
It is guaranteed that there are at most 8 cases with n>100.
Output
For each test case, output n lines, where the ith line contains two integers besti,worsti(1≤besti≤worsti≤n), denoting the best possible and worst possible rank a team would get after the tournament finishes.