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.
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:
Additional constraint on the input: the sum of $$$(n + m + 1)$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.
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.
41 02 11 20 24 5 55 4 11 22 1 5 45 2 3 13 14 3 3 4 15 5 4 5 2
1 2 5 6 9 8 11 11 12 13 13 13 12 15
Let's consider the third test case of the example:
Name |
---|