P8536 "Wdoi-2" Genrou Gatsunei

**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.

## 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

**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$.

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.**

## Sample Explanation - For testdata $1$, obviously $a_2>1,a_3>2$. - For testdata $2$, obviously $a_22$. - For testdata $3$, obviously $a_2>1,a_33$.\ 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