Problem Description

You are given a $\tt{01}$ 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$ not greater than $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 there is no solution.

A permutation of $1 \sim n$ means a sequence in which every positive integer not greater than $n$ appears exactly once.

Input Format

This problem has multiple test cases.

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

Then each test case is given as follows:

• The first line contains two integers $n, l$.
• The second line contains a $\tt{01}$ string of length $n$, denoted as $S$.

Output Format

For each test case, output one line:

• If there exists a permutation $p$ that satisfies the conditions, output $n$ integers separated by spaces, representing the permutation $p$ you constructed.
• Otherwise, output $-1$.

Any output that meets the requirements will be accepted.

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

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

Hint

"Sample Explanation #1"

For the $1$st test case, $f_{p,3}(1)=f_{p,2}(4)=f_{p,1}(5)=f_{p,0}(1)=1$, and the other positions are similar, so when $p$ is $\{4,3,2,5,1\}$, it satisfies the conditions.

For the $2$nd test case, it can be proved that there is no permutation $p$ that satisfies the conditions.

For the $3$rd test case, $\{2,1,4,5,3\}$ is also a permutation $p$ that satisfies the conditions.

Constraints

Let $\sum n$ denote the sum of $n$ within a single test point.

For all testdata, $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$, and $S$ is guaranteed to contain only $\tt{0}$ and $\tt{1}$.

You can get the score only if you pass all test points of this problem.

Translated by ChatGPT 5