K Subsequences#12942

K Subsequences

1 second
256 megabytes
Hard

For an array , define as the maximum sum on a subsegment of this array. For example, f([-1, -1, -1]) = 0, f([-1, 1, 1, 1, -1]) = 3.

You are given an array of length , containing only s and s. Partition it into subsequences a_1, a_2, \ldots, a_k such that max_{1 \leq i \leq k} f(a_i) is the minimum possible. If there are many solutions, output any.

Input

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

The first line of each test case contains two integers and (1 \leq k \leq n \leq 2\cdot 10^5)  — the length of the array and the number of subsequences.

The second line of each test case contains integers a_1, a_2, \ldots, a_{n} (a_i = \pm 1)  — elements of the array.

It is guaranteed that the sum of over all test cases does not exceed 2\cdot 10^5.

Output

For each test case, output integers b_1, b_2, \ldots, b_n (1 \leq b_i \leq k). Here b_i means that element a_i belongs to the b_i-th subsequence.

Note that subsequences are allowed to be empty: it's allowed for some number to not appear in .

Examples

Example

Loading
Loading

Note

In the first test case, we can put all elements into a single subsequence [1, -1, 1], with max subsegment sum (the max subsegment sum for the remaining, empty subsequence is ).

In the second test case, we can split elements into two subsequences [-1, 1], [1, -1], both with max subsegment sum .

In the third test case, we can split elements into three subsequences [1, 1], [1, 1], [1, 1, 1], with max subsegment sums correspondingly.

In the fourth test case, we can split elements into three subsequences [1, 1, -1, 1], [1, 1, -1, 1], [1, 1], all with max subsegment sum .

In the fifth test case, we can split elements into four subsequences [1, -1, 1], [1, -1, 1], [1, -1, 1], [1, -1, 1], all with max subsegment sum .