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.
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.
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 .
Example
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 .