题目背景

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$。