题目描述

bool binary_search(int n, int p[], int target){
    int left = 1, right = n;
    while(left < right){
        int mid = (left + right) / 2;
        if(p[mid] == target)
            return true;
        else if(p[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    if(p[left] == target) return true;
    else return false;
}

众所周知，如果 $p$ 恰好是排好序的，这段代码将返回 true，当且仅当 target 在 $p$ 中出现。换句话说，如果 $p$ 不是排好序的，那么可能就不是这样了。

给一个正整数 $n$ 和一个序列 $b_1,\ldots ,b_n \in \{\texttt{true},\texttt{false}\}$。保证存在一个正整数 $k$ 满足 $n = 2^k - 1$。你必须生成一个 $\{1,\ldots,n\}$ 的排列 $p$ 满足一些条件。令 $S(p)$ 为对于 $i \in \{1,\ldots,n\}$，调用 binary_search(n, p, i) 时不返回 $b_i$ 的 $i$ 的个数。你必须找到一个 $p$ 使得 $S(p)$ 尽可能小（详见「数据范围与提示」中的说明）。

注意，一个 $\{1,\ldots,n\}$ 的排列是指一个 $n$ 个整数组成的数列，满足从 $1$ 到 $n$ 的整数在数列中恰好出现一次。

---

输入格式

输入包含多组数据。第一行包含一个整数 $T$，表示测试数据组数。接下来有 $T$ 组数据。

对于每组数据，第一行一个整数 $n$，第二行一个长度为 $n$ 且只包含 01 的字符串。这些字符不用空格隔开。如果第 $i$ 个字符为 1，则 $b_i = \texttt{true}$，如果是 0，则 $b_i = \texttt{false}$。

---

输出格式

输出包含对于这 $T$ 组数据的答案。每行一个排列 $p$，表示对该组测试数据的答案。

---

样例 1

输入

4
3
111
7
1111111
3
000
7
0000000

输出

1 2 3
1 2 3 4 5 6 7
3 2 1
7 6 5 4 3 2 1

解释
在前两组测试数据中，我们有 $S(p) = 0$。

在第三组数据中，有 $S(p) = 1$。这是因为 binary_search(n, p, 2) 返回 true，而 $b_2 = \texttt{false}$。

在第四组数据中，有 $S(p) = 1$。这是因为 binary_search(n, p, 4) 返回 true，而 $b_4 = \texttt{false}$。

---

样例 2

输入

2
3
010
7
0010110

输出

3 2 1
7 3 1 5 2 4 6

对于这两组数据，我们有 $S(p) = 0$。

---

数据范围与提示

• 令 $\sum n$ 表示在输入中所有 $n$ 的和
• $1 \le \sum n \le 10^5$
• $1 \le T \le 7000$
• 存在 $k \in \mathbb{N}, k > 0$，满足 $n = 2^k - 1$

如果对于子任务的所有测试点，都有 $S(p) \le 1$，那么你会得到该子任务的全部分数。
否则，如果对于子任务的所有测试点，都有 $0 \le S(p) \le \lceil\log_2 n\rceil$（即 $1 \le 2^{S(p)} \le n+1$），那么你会得到该子任务 $50\%$ 的分数。

#	分值	限制
1	3	$b_i = \texttt{true}$
2	4	$b_i = \texttt{false}$
3	16	$1 \le n \le 7$
4	25	$1 \le n \le 15$
5	22	$n = 2^{16} - 1$，并且 $b_i$ 在 $\{\texttt{true},\texttt{false}\}$ 中均匀随机生成
6	30	无附加限制

---