CF1622B.Berland Music

Berland Music is a music streaming service built specifically to support Berland local artist. Its developers are currently working on a song recommendation module.

So imagine Monocarp got recommended $n$ songs, numbered from $1$ to $n$. The $i$-th song had its predicted rating equal to $p_i$, where $1 \le p_i \le n$ and every integer from $1$ to $n$ appears exactly once. In other words, $p$ is a permutation.

After listening to each of them, Monocarp pressed either a like or a dislike button. Let his vote sequence be represented with a string $s$, such that $s_i=0$ means that he disliked the $i$-th song, and $s_i=1$ means that he liked it.

Now the service has to re-evaluate the song ratings in such a way that:

• the new ratings $q_1, q_2, \dots, q_n$ still form a permutation ($1 \le q_i \le n$; each integer from $1$ to $n$ appears exactly once);
• every song that Monocarp liked should have a greater rating than every song that Monocarp disliked (formally, for all $i, j$ such that $s_i=1$ and $s_j=0$, $q_i \gt q_j$ should hold).

Among all valid permutations $q$ find the one that has the smallest value of $\sum\limits_{i=1}^n |p_i-q_i|$, where $|x|$ is an absolute value of $x$.

Print the permutation $q_1, q_2, \dots, q_n$. If there are multiple answers, you can print any of them.

Berland Music 是一项专为支持 Berland 本地艺术家而打造的音乐流媒体服务。其开发人员目前正在开发一个歌曲推荐模块。

假设 Monocarp 被推荐了 $n$ 首歌曲，编号从 $1$ 到 $n$。第 $i$ 首歌曲的预测评分为 $p_i$，其中 $1 \le p_i \le n$，且 $1$ 到 $n$ 中的每个整数恰好出现一次。换言之，$p$ 是一个排列。

在听完每首歌曲后，Monocarp 要么点击“喜欢”，要么点击“不喜欢”。设他的投票序列为字符串 $s$，其中 $s_i = 0$ 表示他不喜欢第 $i$ 首歌曲，$s_i = 1$ 表示他喜欢该歌曲。

现在，该服务需重新评估歌曲评分，使得：

• 新的评分 $q_1, q_2, \dots, q_n$ 仍构成一个排列（即 $1 \le q_i \le n$，且 $1$ 到 $n$ 中的每个整数恰好出现一次）；
• Monocarp 喜欢的每首歌曲的评分必须严格大于他不喜欢的每首歌曲的评分（形式化地，对所有满足 $s_i = 1$ 和 $s_j = 0$ 的 $i, j$，均有 $q_i > q_j$）。

在所有满足条件的排列 $q$ 中，找出使 $\sum\limits_{i=1}^n |p_i - q_i|$ 最小的那个（其中 $|x|$ 表示 $x$ 的绝对值）。

输出排列 $q_1, q_2, \dots, q_n$。若存在多个答案，输出任意一个即可。

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of testcases.

The first line of each testcase contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of songs.

The second line of each testcase contains $n$ integers $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$) — the permutation of the predicted ratings.

The third line contains a single string $s$, consisting of $n$ characters. Each character is either a $0$ or a $1$. $0$ means that Monocarp disliked the song, and $1$ means that he liked it.

The sum of $n$ over all testcases doesn't exceed $2 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）——测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）——歌曲的数量。

每个测试用例的第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$（$1 \le p_i \le n$）——预测评分的一个排列。

第三行包含一个长度为 $n$ 的字符串 $s$，其中每个字符为 $0$ 或 $1$。$0$ 表示 Monocarp 不喜欢该歌曲，$1$ 表示他喜欢该歌曲。

所有测试用例的 $n$ 值之和不超过 $2 \cdot 10^5$。

For each testcase, print a permutation $q$ — the re-evaluated ratings of the songs. If there are multiple answers such that $\sum\limits_{i=1}^n |p_i-q_i|$ is minimum possible, you can print any of them.

对于每个测试用例，输出一个排列 $q$ —— 歌曲重新评估后的评分。如果存在多个满足 $\sum\limits_{i=1}^n |p_i-q_i|$ 为最小可能值的答案，你可以输出其中任意一个。

In the first testcase, there exists only one permutation $q$ such that each liked song is rating higher than each disliked song: song $1$ gets rating $2$ and song $2$ gets rating $1$. $\sum\limits_{i=1}^n |p_i-q_i|=|1-2|+|2-1|=2$.

In the second testcase, Monocarp liked all songs, so all permutations could work. The permutation with the minimum sum of absolute differences is the permutation equal to $p$. Its cost is $0$.

在第一个测试用例中，仅存在一个排列 $q$，使得每个喜欢的歌曲的评分均高于每个不喜欢的歌曲：歌曲 $1$ 的评分为 $2$，歌曲 $2$ 的评分为 $1$。$\sum\limits_{i=1}^n |p_i-q_i|=|1-2|+|2-1|=2$。

在第二个测试用例中，Monocarp 喜欢所有歌曲，因此所有排列均满足条件。绝对差之和最小的排列即为与 $p$ 相同的排列，其代价为 $0$。