「Cfz Round 3」Circle

题目描述

给定一个长度为 $n$ 的 $\tt{01}$ 串 $S$ 和一个非负整数 $l$。 我们定义,对于一个 $1\sim n$ 的排列 $t$ 和非负整数 $k$: $$f_{t,k}(i)=\begin{cases}i & k=0\\f_{t,k-1}(t_i) & k \neq 0\end{cases}$$ 你需要构造一个 $1\sim n$ 的排列 $p$,满足: - 对于任意一个不大于 $n$ 的正整数 $i$,都满足 $p_i \neq i$; - 若 $S_i$ 为 $\tt1$,则 $f_{p,l}(i)=i$(若 $S_i$ 为 $\tt0$ 则没有限制); 或报告无解。 其中,$1\sim n$ 的排列指满足所有不大于 $n$ 的正整数恰好出现一次的序列。

输入输出格式

输入格式


**本题有多组测试数据。** 第一行输入一个整数 $T$,表示测试数据组数。 接下来依次输入每组测试数据。对于每组测试数据: - 第一行输入两个整数 $n,l$。 - 第二行输入一个长度为 $n$ 的 $\tt{01}$ 串表示 $S$。

输出格式


对于每组数据,输出一行: - 若存在满足条件的排列 $p$,则输出用空格分隔的 $n$ 个整数,表示你构造的排列 $p$; - 若不存在满足条件的排列 $p$,则输出 $-1$。 **所有满足要求的输出均可通过。** 在本题中,由于 checker 的特性,多个空格和换行只会被当做一个空格或换行。你可以利用这个特性来减少你的代码长度。

输入输出样例

输入样例 #1

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

输出样例 #1

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

说明

#### 「样例解释 #1」 对于第 $1$ 组数据,$f_{p,3}(1)=f_{p,2}(4)=f_{p,1}(5)=f_{p,0}(1)=1$,其余数同理,所以 $p$ 为 $\{4,3,2,5,1\}$ 时满足条件。 对于第 $2$ 组数据,可以证明不存在满足条件的排列 $p$。 对于第 $3$ 组数据,$\{2,1,4,5,3\}$ 等也为满足条件的排列 $p$。 #### 「数据范围」 设 $\sum n$ 表示单个测试点中 $n$ 的和。 对于所有数据,$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$,保证 $S$ 中只包含 $\tt{0}$ 和 $\tt{1}$。 **只有你通过本题的所有测试点,你才能获得本题的分数。**