题目描述

在算法王国的热带雨林深处，生活着一群聪明但不太靠谱的猴子。它们以发明各种另类算法而闻名——其中最著名的就是猴子排序。

聪明的猴群开始研究新的算法，它们盯上了二分查找。

于是，猴子二分迅速在猴群中流行起来。在某些特殊情况下，它甚至可能比传统二分查找更快。

给定一个整数 $n$ 和一个长度为 $n$ 的二进制字符串 $s$（仅包含字符 0 或 1）。

对于长度为 $n$ 的排列 $p$（由 $1$ 到 $n$ 的 $n$ 个互不相同的整数组成）和整数 $x$，我们按照如下伪代码定义 $\text{find}(x)$：

find(x):
    l = 1
    r = n
    while l <= r:
        随机选择一个整数 m ∈ [l, r]（闭区间）
        if p[m] == x:
            return m
        else if p[m] > x:
            r = m - 1
        else:
            l = m + 1
    return undefined  // 未找到

我们称整数 $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$ 是稳定的。

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

输入描述

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试数据组数。

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

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

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

输出描述

对于每个测试用例：

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

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

样例

3
3
111
11
00001001100
5
10100

YES
1 2 3
YES
2 1 4 3 5 7 6 8 9 11 10
NO

注释

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

• 若随机选择 $m=1$，$p_1=1<2$，则 $\ell$ 变为 $2$，此时 $\ell=2,r=3$；
  • 若再选 $m=2$，直接返回 $2$；
  • 若再选 $m=3$，$p_3=3>2$，$r$ 变为 $2$，此时 $\ell=2,r=2$，只能选 $m=2$，返回 $2$。
• 若随机选择 $m=2$，直接返回 $2$；
• 若随机选择 $m=3$，过程与 $m=1$ 类似，最终总是返回 $2$。

因此，无论随机选择如何，$\text{find}(2)$ 的返回值始终是 $2$，整数 $2$ 稳定。同理可证 $1$ 和 $3$ 也稳定。故 $p=[1,2,3]$ 合法。