$$$K$$$ Subsequences
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

For an array $$$b$$$, define $$$f(b)$$$ 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 $$$a$$$ of length $$$n$$$, containing only $$$1$$$s and $$$-1$$$s. Partition it into $$$k$$$ 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 $$$t$$$ ($$$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 $$$n$$$ and $$$k$$$ ($$$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 $$$n$$$ integers $$$a_1, a_2, \ldots, a_{n}$$$ ($$$a_i = \pm 1$$$)  — elements of the array.

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

Output

For each test case, output $$$n$$$ 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 $$$\leq k$$$ to not appear in $$$b$$$.

Example
Input
5
3 2
1 -1 1
4 2
-1 1 1 -1
7 3
1 1 1 1 1 1 1
10 3
1 1 1 1 -1 -1 1 1 1 1
12 4
1 1 1 1 -1 -1 -1 -1 1 1 1 1
Output
1 1 1
1 1 2 2
1 1 2 2 3 3 3
1 2 1 2 1 2 1 2 3 3
1 2 3 4 1 2 3 4 1 2 3 4
Note

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

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

In the third test case, we can split elements into three subsequences $$$[1, 1], [1, 1], [1, 1, 1]$$$, with max subsegment sums $$$2, 2, 3$$$ 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 $$$2$$$.

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 $$$1$$$.