MEX and Increments

Dmitry has an array of nn non-negative integers a1,a2,…,ana1,a2,…,an.

In one operation, Dmitry can choose any index jj (1≤j≤n1≤j≤n) and increase the value of the element ajaj by 11. He can choose the same index jj multiple times.

For each ii from 00 to nn, determine whether Dmitry can make the MEXMEX of the array equal to exactly ii. If it is possible, then determine the minimum number of operations to do it.

The MEXMEX of the array is equal to the minimum non-negative integer that is not in the array. For example, the MEXMEX of the array [3,1,0][3,1,0] is equal to 22, and the array [3,3,1,4][3,3,1,4] is equal to 00.

Input

The first line of input data contains a single integer tt (1≤t≤1041≤t≤104) — the number of test cases in the input.

The descriptions of the test cases follow.

The first line of the description of each test case contains a single integer nn (1≤n≤2⋅1051≤n≤2⋅105) — the length of the array aa.

The second line of the description of each test case contains nn integers a1,a2,…,ana1,a2,…,an (0≤ai≤n0≤ai≤n) — elements of the array aa.

It is guaranteed that the sum of the values nn over all test cases in the test does not exceed 2⋅1052⋅105.

Output

For each test case, output n+1n+1 integer — ii-th number is equal to the minimum number of operations for which you can make the array MEXMEX equal to ii (0≤i≤n0≤i≤n), or -1 if this cannot be done.

input:

5
3
0 1 3
7
0 1 2 3 4 3 2
4
3 0 0 0
7
4 6 2 3 5 0 5
5
4 0 1 0 4

output:

1 1 0 -1 
1 1 2 2 1 0 2 6 
3 0 1 4 3 
1 0 -1 -1 -1 -1 -1 -1 
2 1 0 2 -1 -1 

关键：到底是谁来构成mex所需要的0~i-1的元素？让最接近i的数来构造！

设想一下，假设有1，3我们现在要构造2和4，1可以用来构造2也可以用来构造4，如果1被用来构造4的话，2就不能构造出来。因此我们要用最接近4的数来构造，即用3来构造4。同时我们会发现，用最接近当前i的数来i，他所需的次数也是最优的。这是一种贪心策略。

我们要求使mex(a数组) = i，最少的步数，只需构造出0~i - 1中的每个数，再把所有等于 i 的数全部加1，即可。

先求第一部分：0~i-1，基于动态规划的思想，我们设dp[i]表示构造0~i - 1所需的最小步数。dp[0] = 0, dp[i] = dp[i-1] + i - 1 - 最接近i的那个数。当然最靠近i的那个数一旦被用了，下次就不能再用了。

第二部分，只需要看cnt[i]，的个数就行，即把所有i加1就可以得到mex（a数组） = i。当然这一部分不是真的给i+1，整个过程cnt[i]是先存入优先队列中，数只有第一部分求dp[i]的时候把优先队列中的值取出来构造0~i-1这一步会变。