Given a binary string $S$ of length $n$ and a non-negative integer $l$.

We define, for a permutation $t$ of $1 \sim n$ and a non-negative integer $k$:

$$f_{t,k}(i)=\begin{cases}i & k=0\\f_{t,k-1}(t_i) & k \neq 0\end{cases}$$

You need to construct a permutation $p$ of $1 \sim n$ such that:

• For any positive integer $i \le n$, $p_i \neq i$;
• If $S_i$ is $\tt1$, then $f_{p,l}(i)=i$ (if $S_i$ is $\tt0$, there is no restriction);

Or report that no such permutation exists.

A permutation of $1 \sim n$ is a sequence where every positive integer no greater than $n$ appears exactly once.

Input

This problem contains multiple test cases.

The first line contains an integer $T$, representing the number of test cases.

For each test case:

• The first line contains two integers $n, l$.
• The second line contains a binary string $S$ of length $n$.

Output

For each test case, output one line:

• If a valid permutation $p$ exists, output $n$ space-separated integers representing the permutation $p$;
• If no such permutation $p$ exists, output $-1$.

Any valid output will be accepted.

Examples

Input 1

4
5 3
10011
4 5
1000
5 6
11111
9 6
011111011

Output 1

4 3 2 5 1
-1
5 4 2 3 1
3 1 2 6 4 5 9 7 8

Note 1

For the first test case, $f_{p,3}(1)=f_{p,2}(4)=f_{p,1}(5)=f_{p,0}(1)=1$, and the same applies to the other numbers, so $p = \{4, 3, 2, 5, 1\}$ satisfies the conditions.

For the second test case, it can be proven that no such permutation $p$ exists.

For the third test case, $\{2, 1, 4, 5, 3\}$ and others are also valid permutations $p$.

Constraints

Let $\sum n$ denote the sum of $n$ over all test cases.

For all data, $1 \le T \le 100$, $2 \le n \le 5\times 10^5$, $0 \le l \le 10^{18}$, $\sum n \le 5\times 10^5$. It is guaranteed that $S$ contains only $\tt0$ and $\tt1$.