311375: CF1976C. Job Interview

C. Job Interviewtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Monocarp is opening his own IT company. He wants to hire $n$ programmers and $m$ testers.

There are $n+m+1$ candidates, numbered from $1$ to $n+m+1$ in chronological order of their arriving time. The $i$-th candidate has programming skill $a_i$ and testing skill $b_i$ (a person's programming skill is different from their testing skill). The skill of the team is the sum of the programming skills of all candidates hired as programmers, and the sum of the testing skills of all candidates hired as testers.

When a candidate arrives to interview, Monocarp tries to assign them to the most suitable position for them (if their programming skill is higher, then he hires them as a programmer, otherwise as a tester). If all slots for that position are filled, Monocarp assigns them to the other position.

Your task is, for each candidate, calculate the skill of the team if everyone except them comes to interview. Note that it means that exactly $n+m$ candidates will arrive, so all $n+m$ positions in the company will be filled.

Input

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

Each test case consists of three lines:

• the first line contains two integers $n$ and $m$ ($0 \le n, m \le 2 \cdot 10^5$; $2 \le n + m + 1 \le 2 \cdot 10^5$) — the number of programmers and the number of testers Monocarp wants to hire, respectively;
• the second line contains $n + m + 1$ integers $a_1, a_2, \dots, a_{n+m+1}$ ($1 \le a_i \le 10^9$), where $a_i$ is the programming skill of the $i$-th candidate;
• the third line contains $n + m + 1$ integers $b_1, b_2, \dots, b_{n+m+1}$ ($1 \le b_i \le 10^9$; $b_i \ne a_i$), where $b_i$ is the testing skill of the $i$-th candidate.

Additional constraint on the input: the sum of $(n + m + 1)$ over all test cases doesn't exceed $2 \cdot 10^5$.

Output

For each test case, print $n + m + 1$ integers, where the $i$-th integer should be equal to the skill of the team if everyone except the $i$-th candidate comes to interview.

ExampleInput

4
1 0
2 1
1 2
0 2
4 5 5
5 4 1
1 2
2 1 5 4
5 2 3 1
3 1
4 3 3 4 1
5 5 4 5 2

Output

1 2 
5 6 9 
8 11 11 12 
13 13 13 12 15 

Note

Let's consider the third test case of the example:

• if the $1$-st candidate does not arrive, the $2$-nd candidate gets hired as a tester, the $3$-rd candidate gets hired as a programmer, the $4$-th candidate gets hired as a tester. The total skill of the team will be $2 + 5 + 1 = 8$;
• if the $2$-nd candidate does not arrive, the $1$-st candidate gets hired as a tester, the $3$-rd candidate gets hired as a programmer, the $4$-th candidate gets hired as a tester. The total skill of the team will be $5 + 5 + 1 = 11$;
• if the $3$-rd candidate does not arrive, the $1$-st candidate gets hired as a tester, the $2$-nd candidate gets hired as a tester, the $4$-th candidate gets hired as a programmer. The total skill of the team will be $5 + 2 + 4 = 11$;
• if the $4$-th candidate does not arrive, the $1$-st candidate gets hired as a tester, the $2$-nd candidate gets hired as a tester, the $3$-rd candidate gets hired as a programmer. The total skill of the team will be $5 + 2 + 5 = 12$.

题目大意：
Monocarp正在开设自己的IT公司，他想雇佣n名程序员和m名测试员。总共有n+m+1名候选人，按照到达时间的先后编号为1到n+m+1。第i个候选人有编程技能a_i和测试技能b_i（一个人的编程技能与测试技能不同）。团队的技能是所有被雇佣为程序员的候选人的编程技能之和，以及所有被雇佣为测试员的候选人的测试技能之和。

当一个候选人来面试时，Monocarp会尝试为他们分配最合适的位置（如果他们的编程技能更高，那么他会雇佣他们为程序员，否则为测试员）。如果该位置的所有名额都已满，Monocarp会为他们分配另一个位置。

你的任务是，对于每个候选人，计算如果除了他们之外的所有人来面试，团队的技能是多少。这意味着总共有n+m个候选人会到达，所以公司的n+m个位置都将被填满。

输入输出数据格式：
输入：
- 第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。
- 每个测试用例包含三行：
- 第一行包含两个整数n和m（0≤n, m≤2×10^5；2≤n+m+1≤2×10^5）——Monocarp想雇佣的程序员的数量和测试员数量。
- 第二行包含n+m+1个整数a_1, a_2, …, a_{n+m+1}（1≤a_i≤10^9），其中a_i是第i个候选人的编程技能。
- 第三行包含n+m+1个整数b_1, b_2, …, b_{n+m+1}（1≤b_i≤10^9；b_i≠a_i），其中b_i是第i个候选人的测试技能。
- 输入的附加限制：所有测试用例的(n+m+1)之和不超过2×10^5。

输出：
- 对于每个测试用例，打印n+m+1个整数，其中第i个整数应等于如果除了第i个候选人之外的所有人来面试，团队的技能。

示例输入输出：
输入：
```
4
1 0
2 1
1 2
0 2
4 5 5
5 4 1
1 2
2 1 5 4
5 2 3 1
3 1
4 3 3 4 1
5 5 4 5 2
```
输出：
```
1 2
5 6 9
8 11 11 12
13 13 13 12 15
```题目大意： Monocarp正在开设自己的IT公司，他想雇佣n名程序员和m名测试员。总共有n+m+1名候选人，按照到达时间的先后编号为1到n+m+1。第i个候选人有编程技能a_i和测试技能b_i（一个人的编程技能与测试技能不同）。团队的技能是所有被雇佣为程序员的候选人的编程技能之和，以及所有被雇佣为测试员的候选人的测试技能之和。 当一个候选人来面试时，Monocarp会尝试为他们分配最合适的位置（如果他们的编程技能更高，那么他会雇佣他们为程序员，否则为测试员）。如果该位置的所有名额都已满，Monocarp会为他们分配另一个位置。 你的任务是，对于每个候选人，计算如果除了他们之外的所有人来面试，团队的技能是多少。这意味着总共有n+m个候选人会到达，所以公司的n+m个位置都将被填满。 输入输出数据格式： 输入： - 第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。 - 每个测试用例包含三行： - 第一行包含两个整数n和m（0≤n, m≤2×10^5；2≤n+m+1≤2×10^5）——Monocarp想雇佣的程序员的数量和测试员数量。 - 第二行包含n+m+1个整数a_1, a_2, …, a_{n+m+1}（1≤a_i≤10^9），其中a_i是第i个候选人的编程技能。 - 第三行包含n+m+1个整数b_1, b_2, …, b_{n+m+1}（1≤b_i≤10^9；b_i≠a_i），其中b_i是第i个候选人的测试技能。 - 输入的附加限制：所有测试用例的(n+m+1)之和不超过2×10^5。 输出： - 对于每个测试用例，打印n+m+1个整数，其中第i个整数应等于如果除了第i个候选人之外的所有人来面试，团队的技能。 示例输入输出： 输入： ``` 4 1 0 2 1 1 2 0 2 4 5 5 5 4 1 1 2 2 1 5 4 5 2 3 1 3 1 4 3 3 4 1 5 5 4 5 2 ``` 输出： ``` 1 2 5 6 9 8 11 11 12 13 13 13 12 15 ```