对于一个数组 $b$，定义 $f(b)$ 为该数组中子段和的最大值。例如，$f([-1, -1, -1]) = 0$，$f([-1, 1, 1, 1, -1]) = 3$。

给定一个长度为 $n$ 的数组 $a$，其中仅包含 $1$ 和 $-1$。将其划分为 $k$ 个子序列 $a_1, a_2, \dots, a_k$，使得 $\max_{1 \le i \le k} f(a_i)$ 尽可能小。如果存在多种方案，输出任意一种即可。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 10^5$) —— 测试用例的数量。接下来是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $k$ ($1 \le k \le n \le 2 \cdot 10^5$) —— 数组的长度和子序列的数量。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($a_i = \pm 1$) —— 数组的元素。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出 $n$ 个整数 $b_1, b_2, \dots, b_n$ ($1 \le b_i \le k$)。其中 $b_i$ 表示元素 $a_i$ 属于第 $b_i$ 个子序列。

注意，子序列允许为空：允许某些编号 $\le k$ 的子序列在 $b$ 中未出现。

样例

样例输入 1

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

样例输出 1

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

说明

在第一个测试用例中，我们可以将所有元素放入单个子序列 $[1, -1, 1]$ 中，其最大子段和为 $1$（剩余空子序列的最大子段和为 $0$）。

在第二个测试用例中，我们可以将元素拆分为两个子序列 $[-1, 1], [1, -1]$，两者的最大子段和均为 $1$。

在第三个测试用例中，我们可以将元素拆分为三个子序列 $[1, 1], [1, 1], [1, 1, 1]$，其最大子段和分别为 $2, 2, 3$。

在第四个测试用例中，我们可以将元素拆分为三个子序列 $[1, 1, -1, 1], [1, 1, -1, 1], [1, 1]$，所有子序列的最大子段和均为 $2$。

在第五个测试用例中，我们可以将元素拆分为四个子序列 $[1, -1, 1], [1, -1, 1], [1, -1, 1], [1, -1, 1]$，所有子序列的最大子段和均为 $1$。