P10034 "Cfz Round 3" Circle

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.

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

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

#### "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