「Wdoi-2」幻胧月睨

**Problem Number:** $\textit{39}$ **背景与题目无关，选手可以直接看下面的「简要题意」。** 那是在竹取物语之后的故事了，幻想乡距离与现实隔绝也已经过去了百年时光。 地上人向月球发起了侵略战争之后，一只名叫**铃仙**的月兔舍弃了同伴，死里逃生，逃到了在幻想乡内的永远亭，来到了辉夜与永琳的身边，生活得安稳而舒适。 又过了数十年，铃仙接收到了来自月球的使唤，被要求强制返回月球。辉夜与永琳商量了下，决定不将铃仙交还予月球。但为了避免造成麻烦，辉夜与永琳决定将满月消失在地上，只留下一轮虚假的月亮。 ----- 为了方便调查异变，八云紫运用自己的能力，将整个幻想乡变成了永夜。 被穿梭回异变发生当时的四组主角，共八人。除了依然留有记忆，可以来回穿梭在虚与实的境界的八云紫之外，其他的人缺乏了记忆，重新开始踏上夺回幻想乡的满月的征途。 在慧音的指引之下，她们来到了迷途竹林，在她们的面前，是一只名叫铃仙的月兔。

### 简要题意 给定一个长度为 $n$ 的 01 串 $b$，要求构造一个 $n$ 阶排列 $a$，满足，对于 $a_i(2\le i\le n)$，记 $m_i=\max_{j=1}^{i-1}\{a_j\}$，则： - 若 $b_i=1$，则 $a_i>m_i$; - 否则 $a_i<m_i$。 可以证明，总存在一个数列 $a$ 满足以上条件。 **如果有多组解，输出任意一种。** 同时注意到 $b_1$ 的取值是任意的，对数列 $a$ 没有影响。 ### 原始题意 铃仙拥有操纵狂气程度的能力，换而言之，就是操纵物体的波长、振幅以及相位。这种能力为主角制造了种种障碍——例如操纵光波，会让弹幕虚虚实实，甚至会出现虚假的自我，对躲避弹幕造成极大的干扰。 以符卡「幻胧月睨」为例。「幻胧月睨」中一共有 $n$ 个弹幕，每个弹幕都会有一个相位，相位非 $0$ 即 $1$。这些弹幕的相位会构成一个长度为 $n$ 的数列 $\{b_i\}$。 铃仙会操纵这些弹幕的相位，将其变得千奇百怪。具体而言，被操纵了之后的弹幕的相位是一个长度为 $n$ 的**排列** $\{a_i\}$，即 $1 \sim n$ 的数字都会**不重不漏**地出现在这个序列之中。 为了加大主角躲避弹幕的难度，铃仙会设置一个阈值。对于每一个元素 $a_i$，阈值是其**前缀**的**最大**值，即 $a_1,a_2,\dots,a_{i-1}$ 中的最大值。若原来的第 $i$ 个弹幕的相位为 $1$，则被操纵后的弹幕的相位要**大于**这个阈值，否则被操纵后的弹幕的相位要**小于**这个阈值。 显然的是，根据铃仙的操纵规则，无论原本的弹幕的相位如何，都是存在可能的操纵方案的。由于主角们失去了记忆，而找回月亮的时间已经所剩不多了，而且弹幕战对时间的把控要求极高。她们找到了你，希望你能够对铃仙原本的弹幕相位，给出**任意一种**操作后的弹幕相位，来为她们的闪避弹幕进行准备。

**本题有多组数据。** 第一行一个整数 $T$，表示数据组数。 对于每组数据： - 第一行一个整数 $n$，意义如题述。 - 第二行一个长度为 $n$ 的 01 串 $b$。

对于每组数据，输出一行 $n$ 个整数，即你构造的数列 $a$。 **如果有多组解，输出任意一种。**

3
3
111
3
101
4
0101

1 2 3
2 1 3
1 3 2 4

### 样例解释 - 对于数据 $1$，显然 $a_2>1,a_3>2$。 - 对于数据 $2$，显然 $a_2<2,a_3>2$。 - 对于数据 $3$，显然 $a_2>1,a_3<3,a_4>3$。\ 注意到 $a=\{2,3,1,4\}$ 同样满足要求。 ### 数据范围 $$ \def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|}\hline \textbf{Subtask} & \bm{n\le} & \textbf{特殊性质} & \textbf{Subtask 依赖} & \textbf{分值}\\\hline 1 & 10 & - & - & 5\\\hline 2 & 10^5 & \textbf{A} & - & 5 \\\hline 3 & 10^5 & \textbf{B} & - & 20 \\\hline 4 & 10^5 & - & 1,2,3 &70 \\\hline \end{array}$$ - **特殊性质** $\textbf{A}$：保证 $b_i$ 都相等。 - **特殊性质** $\textbf{B}$：存在整数 $p\in[2,n]$，使得对于 $1\le i<p$，有 $b_i=1$；对于 $n\ge i\ge p$，有 $b_i=0$。 对于全部数据，满足 $1\le T\le 10^4$，$1\le n\le 10^5$，$\forall i\in[1,n],b_i\in\{0,1\}$。 保证单个测试点内 $\sum n\le 5\times 10^5$。