Dota2 Pro Circuit

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 $i$th team has earned $a_i$ points from the regional contests. Also, the team that gets the $i$th rank in the tournament can gain $b_i$ 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.

The first line contains a number $T(1\leq T\leq 20)$, denoting the number of test cases.

The first line of each test case contains one number $n(1\leq n\leq 5000)$, denoting the number of different teams that participate in the regional contests and tournaments.

The next line contains $n$ integers $a_1,a_2,\dots,a_n(0\leq a_i\leq 10^9)$, denoting the points of each team before the tournament starts.

Then follows one line containing $n$ integers $b_1,b_2,\dots,b_n(0\leq b_n\leq b_{n-1}\leq ...\leq b_1 \leq 10^9)$, where $b_i$ denotes the number of points a team would get if ranking $i$th in the tournament.

It is guaranteed that there are at most 8 cases with $n>100$.

For each test case, output $n$ lines, where the $i$th line contains two integers $best_i,worst_i(1\leq best_i\leq worst_i\leq n)$, denoting the best possible and worst possible rank a team would get after the tournament finishes.

2
3
5 10 8
5 2 1
2
5 6
4 4

2 3
1 2
1 3
2 2
1 1

2021“MINIEYE杯”中国大学生算法设计超级联赛（9）