CFCF2146C.Wrong Binary Search

给定一个整数 $n$ 和一个长度为 $n$ 的二进制字符串 $s$。

对于长度为 $n$ 的排列 $p$ 和整数 $x$，我们按照如下伪代码定义 $\text{find}(x)$：

function find(int x):
    l := 1
    r := n
    while l <= r:
        let m be a random integer between l and r (inclusive)
        if p[m] == x
            return m
        if p[m] > x:
            r := m - 1
        else:
            l := m + 1
    return undefined     // not found

我们称整数 $x$（$1 \le x \le n$）是 稳定 的，当且仅当无论在上述伪代码中每次如何选择 $m$，$\text{find}(x)$ 总是不为 undefined 且始终有 $p_{\text{find}(x)}=x$ 成立。

你需要构造一个长度为 $n$ 的排列 $p$，使得：

• 对于每个 $1 \le i \le n$，当且仅当 $s_i=\mathtt{1}$ 时，整数 $i$ 是稳定的。

或者判断不存在这样的排列。

$^{\text{∗}}$ 二进制字符串是指仅包含字符 $\mathtt{0}$ 或 $\mathtt{1}$ 的字符串。

$^{\text{†}}$ 长度为 $n$ 的排列是由 $1$ 到 $n$ 的 $n$ 个互不相同的整数组成的序列。例如，$[2,3,1,5,4]$ 是一个排列，而 $[1,2,2]$ 不是排列（$2$ 出现了两次），$[1,3,4]$ 也不是排列（$n=3$，但出现了 $4$）。

每个测试点包含若干测试用例。第一行包含测试用例数 $t$（$1 \le t \le 10^4$）。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 2\cdot 10^5$），表示排列的长度。

第二行包含一个长度为 $n$ 的二进制字符串 $s$（$s_i=\mathtt{0}$ 或 $s_i=\mathtt{1}$）。

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

对于每个测试用例：

• 如果不存在这样的排列，输出一行 "NO"。
• 否则，第一行输出 "YES"。然后在第二行输出 $n$ 个不同的整数 $p_1, p_2, \ldots, p_n$（$1\le p_i\le n$），表示你构造的排列。

输出中的单词大小写不敏感。例如，"yEs"、"yes"、"Yes"、"YES" 都被认为是肯定的输出。

如果有多组满足条件的答案，可以输出任意一种。

在第一个测试用例中，可以构造 $p=[1,2,3]$。以 $\text{find(2)}$ 为例：

• 首先，$l=1$，$r=3$；
• 随机选择 $l=1$ 到 $r=3$ 之间的 $m$。
  • 如果选择 $m=1$：
    • $p_1=1<2$，所以 $l$ 更新为 $m+1=2$，现在 $l=2$, $r=3$；
    • 随机在 $l=2$ 和 $r=3$ 之间选择 $m$。
    • 如果选择 $m=2$：$p_2=2$，直接返回 $2$。
    • 如果选择 $m=3$：$p_3=3>2$，$r$ 更新为 $m-1=2$，此时 $l=2$，$r=2$，只能选择 $m=2$，$p_2=2$，返回 $2$。
  • 如果选择 $m=2$：
    • $p_2=2$，直接返回 $2$。
  • 如果选择 $m=3$，过程与 $m=1$ 类似，最终总是返回 $2$。
• 所以，无论过程中如何选择 $m$，$\text{find}(2)$ 的返回值始终是 $2$。

因此，$p_{\text{find}(2)}=p_2=2$ 始终成立，整数 $2$ 是稳定的。

同理，可以证明 $1$ 和 $3$ 也是稳定的。因此，$p = [1,2,3]$ 是一个合法答案。

在第二个测试用例中，可以构造 $p=[2,4,3,5,1]$。以 $\text{find}(3)$ 为例：

• 首先，$l=1,r=5$；
• 随机选择 $l=1$ 到 $r=5$ 的 $m$，假设选择 $m=2$；
• $p_2=4>3$，所以 $r$ 变为 $m-1=1$，此时 $l=1,r=1$；
• 随机选择 $l=1$ 到 $r=1$ 的 $m$，只能选 $m=1$；
• $p_1=2<3$，$l$ 变为 $m+1=2$，现在 $l=2,r=1$；
• 由于 $l>r$，循环结束，返回 undefined。

所以，$\text{find}(3)$ 的返回值为 undefined，整数 $3$ 不是稳定的。

同理可以分析 $1$，$2$，$4$，$5$ 也都不是稳定的。因此，$p = [2,4,3,5,1]$ 是一个合法解。

其它排列比如 $[5,4,3,2,1]$，$[3,5,1,4,2]$ 也都是合法的答案，你可以输出任何一个。

在第三个测试用例中，可以证明不存在这样的排列。