There are two teams, each consisting of N players, playing a round of Counter-Strike 2 (CS2).
You are given the total damage dealt by the players of one team to the opposing team. Specifically, you are given an array damage, where damage[i] is the total damage dealt by the i-th player to enemy players only.
Players cannot deal damage to their own teammates or themselves.
Each player on the round starts with exactly 100 Health Points (HP).
A player dies when their HP is reduced to 0, and the kill is awarded to the player who deals the final point of damage.
Multiple players may damage the same enemy, and a player may damage multiple enemies.
The given damage values may be distributed among the enemy team in any valid way that is consistent with these rules.
For every player, determine the minimum and maximum possible number of kills they could have achieved over all valid damage distributions.
The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases.
The description of the test cases follows:
The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of players.
The second line of each test case contains $$$n$$$ space-separated integers $$$d_1, d_2, \dots, d_n$$$ ($$$0 \le d_i \le n \times 100$$$) — where $$$d_i$$$ represents the total damage dealt by the $$$i$$$-th player.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \times 10^5$$$, and the total sum of the array $$$d$$$ in any test case does not exceed $$$n \times 100$$$.
For each test case, output $$$n$$$ lines.The $$$i$$$-th line should contain two space-separated integers: the minimum possible number of kills and the maximum possible number of kills that the $$$i$$$-th player could have achieved in that round.
15100 100 1 100 2
0 30 30 10 30 2
In the first test case:We have $$$n = 5$$$ players with damages: $$$d = [100, 100, 1, 100, 2]$$$.The total damage dealt by the entire team is $$$100 + 100 + 1 + 100 + 2 = 303$$$.
Since each enemy has $$$100 \text{ HP}$$$, the maximum total number of enemies the team could have eliminated is at most $$$\lfloor 303 / 100 \rfloor = 3$$$ enemies.
Let us analyze the minimum and maximum kills for each player:
Players 1, 2, and 4
Each of these players dealt exactly $$$100$$$ damage.
Minimum kills = 0
A player can avoid getting any kill by never dealing the final hit. For example, they may deal most of the damage to an enemy, while another teammate delivers the last point of damage and receives the kill.
Maximum kills = 3
Since there are only $$$3$$$ possible kills in the entire round, the largest number of kills any player can obtain is $$$3$$$.
This is achievable because a kill only requires dealing the final point of damage. The player's $$$100$$$ damage can be split into many small portions, allowing them to deal the last point of damage to all three eliminated enemies while the remaining damage is provided by teammates.
Hence, for Players $$$1$$$, $$$2$$$, and $$$4$$$, the answer is [0,3].
Player 3
Player $$$3$$$ dealt only $$$d_3 = 1$$$ damage.
Minimum kills = 0
The single point of damage can be dealt to a surviving enemy, resulting in no kill.
Maximum kills = 1
A kill requires at least one point of final damage. Since Player $$$3$$$ has only one damage point in total, they can secure at most one kill by dealing the final hit to an enemy that already has only $$$1$$$ HP remaining.
Therefore, Player $$$3$$$ has range [0,1].
Player 5
Player $$$5$$$ dealt $$$d_5 = 2$$$ damage.
Minimum kills = 0
They may contribute damage without landing any final blow.
Maximum kills = 2
Their two damage points can be used as two separate finishing hits on two different enemies that were already reduced to $$$1$$$ HP by teammates.
Thus Player $$$5$$$ can obtain at most two kills, giving the range [0,2].
