Background

Problem Number: $\textit{39}$.

The background is unrelated to the problem. Contestants can directly read the "Brief Statement" below.

This is the story after The Tale of the Bamboo Cutter. It has already been a hundred years since Gensokyo was separated from reality.

After the people of Earth launched an invasion war against the Moon, a moon rabbit named Reisen abandoned her companions, barely survived, and fled to Eientei in Gensokyo, arriving at Kaguya and Eirin's side, living a peaceful and comfortable life.

Several decades later, Reisen received an order from the Moon, demanding that she be forced to return. After discussing it, Kaguya and Eirin decided not to hand Reisen back to the Moon. But to avoid causing trouble, they decided to make the full moon disappear from the Earth, leaving only a fake moon.

---

To make it easier to investigate the incident, Yukari Yakumo used her power to turn the entire Gensokyo into an eternal night.

Four groups of protagonists, eight people in total, were sent back to the time when the incident happened. Except for Yukari Yakumo, who still kept her memories and could travel back and forth across the boundary between illusion and reality, the others lost their memories and started their journey again to reclaim Gensokyo's full moon.

Guided by Keine, they arrived at the Lost Bamboo Forest. Before them stood a moon rabbit named Reisen.

Problem Description

Brief Statement

Given a binary string $b$ of length $n$, construct a permutation $a$ of length $n$ such that for $a_i(2\le i\le n)$, let $m_i=\max_{j=1}^{i-1}\{a_j\}$. Then:

• If $b_i=1$, then $a_i>m_i$.
• Otherwise, $a_i<m_i$.

It can be proven that there always exists a sequence $a$ satisfying the above conditions.

If there are multiple solutions, output any one.

Also note that the value of $b_1$ is arbitrary and has no effect on the sequence $a$.

Original Statement

Reisen has the ability to manipulate the degree of madness, in other words, to manipulate the wavelength, amplitude, and phase of objects. This ability creates various obstacles for the protagonists—for example, manipulating light waves can make the bullets appear and disappear, and can even create a fake self, greatly interfering with dodging.

Take the spell card "Genrou Gatsunei" as an example. In "Genrou Gatsunei", there are $n$ bullets, and each bullet has a phase, which is either $0$ or $1$. The phases of these bullets form a sequence $\{b_i\}$ of length $n$.

Reisen will manipulate the phases of these bullets, making them very strange. Specifically, after being manipulated, the phases become a permutation $\{a_i\}$ of length $n$, meaning that every number from $1$ to $n$ appears in this sequence exactly once.

To make it harder for the protagonists to dodge, Reisen sets a threshold. For each element $a_i$, the threshold is the maximum value of its prefix, that is, the maximum among $a_1,a_2,\dots,a_{i-1}$. If the phase of the original $i$-th bullet is $1$, then the manipulated phase must be greater than this threshold; otherwise, the manipulated phase must be less than this threshold.

Obviously, according to Reisen's manipulation rules, no matter what the original bullet phases are, there always exists a feasible manipulation plan. Since the protagonists have lost their memories, there is not much time left to retrieve the moon, and bullet battles require very strict time control, they found you and hope that, given Reisen's original bullet phases, you can provide any possible manipulated bullet phases to help them prepare for dodging.

Input Format

This problem has multiple test cases.

The first line contains an integer $T$, denoting the number of test cases.

For each test case:

• The first line contains an integer $n$, with the meaning described above.
• The second line contains a binary string $b$ of length $n$.

Output Format

For each test case, output one line with $n$ integers, which is the sequence $a$ you constructed.

If there are multiple solutions, output any one.

3
3
111
3
101
4
0101

1 2 3
2 1 3
1 3 2 4

Hint

Sample Explanation

• For testdata $1$, obviously $a_2>1,a_3>2$.
• For testdata $2$, obviously $a_2<2,a_3>2$.
• For testdata $3$, obviously $a_2>1,a_3<3,a_4>3$.
  Note that $a=\{2,3,1,4\}$ also satisfies the requirement.

Constraints

$$\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}$$

• Special property $\textbf{A}$: It is guaranteed that all $b_i$ are equal.
• Special property $\textbf{B}$: There exists an integer $p\in[2,n]$ such that for $1\le i<p$, $b_i=1$; and for $n\ge i\ge p$, $b_i=0$.

For all testdata, $1\le T\le 10^4$, $1\le n\le 10^5$, $\forall i\in[1,n],b_i\in\{0,1\}$.

It is guaranteed that within a single test point, $\sum n\le 5\times 10^5$.

Translated by ChatGPT 5