Berland Music
Contest: Educational Codeforces Round 120 (Rated for Div. 2)
Difficulty rating: 1000
Tags: data structures, greedy, math, sortings

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

Input format:
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$$$.

Output format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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$$$.

Example input:
3
2
1 2
10
3
3 1 2
111
8
2 3 1 8 5 4 7 6
01110001

Example output:
2 1
3 1 2
1 6 5 8 3 2 4 7

Editorial:
Since we know that every disliked song should have lower rating than every liked song, we actually know which new ratings should belong to disliked songs and which should belong to the liked ones.
The disliked songs take ratings from $$$1$$$ to the number of zeros in $$$s$$$. The liked songs take ratings from the number of zeros in $$$s$$$ plus $$$1$$$ to $$$n$$$. Thus, we have two independent tasks to solve.
Let the disliked songs have ratings $$$d_1, d_2, \dots, d_k$$$. Their new ratings should be $$$1, 2, \dots, k$$$. We can show that if we sort the array $$$d$$$, then $$$|d'_1 - 1| + |d'_2 - 2| + \dots + |d'_k - k|$$$ will be the lowest possible. The general way to prove it is to show that if the order has any inversions, we can always fix the leftmost of them (swap two adjacent values), and the cost doesn't increase.
So the solution can be to sort triples $$$(s_i, p_i, i)$$$ and restore $$$q$$$ from the order of $$$i$$$ in these.
Overall complexity: $$$O(n \log n)$$$ per testcase.