← 返回题目列表

Codeforces · 1976/C

C. 工作面试

中文机器翻译题面 查看原题

Monocarp 正在开设自己的 IT 公司。他想雇用 $$$n$$$ 程序员和 $$$m$$$ 测试人员。

有$$$n+m+1$$$候选人,按到达时间顺序编号从$$$1$$$到$$$n+m+1$$$。第$$$i$$$ 候选人具有编程技能$$$a_i$$$ 和测试技能$$$b_i$$$(一个人的编程技能不同于他们的测试技能)。团队的技能是所有被聘为程序员的候选人的编程技能的总和,以及所有被聘为测试员的候选人的测试技能的总和。

当候选人来面试时,Monocarp 会尝试将他们分配到最适合他们的职位(如果他们的编程技能较高,那么他会雇用他们作为程序员,否则作为测试员)。如果该位置的所有槽位都已满,Monocarp 会将它们分配给另一个位置。

你的任务是,对于每个候选人,如果除了他们之外的所有人都来面试,则计算团队的技能。请注意,这意味着恰好 $$$n+m$$$ 候选人将到达,因此公司中的所有 $$$n+m$$$ 职位都将被填补。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例由三行组成:

- 第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$0 \le n, m \le 2 \cdot 10^5$$$; $$$2 \le n + m + 1 \le 2 \cdot 10^5$$$) - 分别是 Monocarp 想要雇用的程序员数量和测试人员数量;
- 第二行包含 $$$n + m + 1$$$ 整数 $$$a_1, a_2, \dots, a_{n+m+1}$$$ ($$$1 \le a_i \le 10^9$$$),其中 $$$a_i$$$ 是第 $$$i$$$ 候选人的编程技能;
- 第三行包含 $$$n + m + 1$$$ 整数 $$$b_1, b_2, \dots, b_{n+m+1}$$$ ($$$1 \le b_i \le 10^9$$$; $$$b_i \ne a_i$$$),其中 $$$b_i$$$ 是测试技能第 $$$i$$$ 位候选人。

对输入的附加约束:所有测试用例的 $$$(n + m + 1)$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印 $$$n + m + 1$$$ 整数,其中,如果除第 $$$i$$$ 之外的每个候选人都来面试,则第 $$$i$$$ 个整数应等于团队的技能。

示例

输入 #1

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

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

注意

让我们考虑示例的第三个测试用例:

- 如果第 $$$1$$$-st 候选人没有到达,则第 $$$2$$$-nd 候选人将被聘为测试员,$$$3$$$-rd 候选人将被聘为程序员,第 $$$4$$$-th 候选人将被聘为测试员。团队的总技能为$$$2 + 5 + 1 = 8$$$;
- 如果第 $$$2$$$-nd 候选人没有到达,则第 $$$1$$$-st 候选人将被聘为测试员,$$$3$$$-rd 候选人将被聘为程序员,第 $$$4$$$-th 候选人将被聘为测试员。团队的总技能为$$$5 + 5 + 1 = 11$$$;
- 如果第 $$$3$$$-rd 候选人没有到达,则第 $$$1$$$-st 候选人将被聘为测试员,第 $$$2$$$-nd 候选人将被聘为测试员,第 $$$4$$$-th 候选人将被聘为程序员。团队的总技能为$$$5 + 2 + 4 = 11$$$;
- 如果第 $$$4$$$-th 候选人没有到达,则第 $$$1$$$-st 候选人将被聘为测试员,第 $$$2$$$-nd 候选人将被聘为测试员,第 $$$3$$$-rd 候选人将被聘为程序员。团队的总技能将为 $$$5 + 2 + 5 = 12$$$。