Berland Music

题意翻译

Berland Music 专为支持 Berland 本地艺术家而构建。它的开发人员目前正在开发歌曲推荐模块。 Mooncarp 得到了 $n$ 首推荐的歌曲，其中第 $i$ 首歌曲的预测评分为 $p_i$，其中所有在 $[1,n]$ 中的整数在这 $p_1,p_2,\dots,p_n$ 中都恰好出现了 $1$ 次。换句话说，**$p$ 是一个排列**。在把每首歌都认真听了一遍之后，Mooncarp 通过一个长度为 $n$ 的 $0/1$ 串对每首歌给出了评价，其中，$s_i=0$ 表示 Mooncarp 不喜欢第 $i$ 首歌，$s_i=1$ 反之。 现在，Berland Music 需要重新计算每首歌的预测评分。具体地，第 $i$ 首歌的预测得分为 $q_i$，工作人员需要保证 $q$ 仍然是一个排列，且所有 Mooncarp 喜欢的歌曲的预测得分都必须大于 Mooncarp 不喜欢的歌曲的预测得分。由于工作人员不希望重新计算后的预测评分和原预测得分的差距太大，工作人员还希望 $\sum\limits_{i=1}^n|p_i-q_i|$ 最小。 现在，你需要给出**任意一个**满足上述要求的 $q_1,q_2,\dots,q_n$。 数据范围： - $t$ 组数据，$1\leqslant t\leqslant 10^4$。 - $1\leqslant n,\sum n\leqslant 2\times 10^5$。 - $1\leqslant p_i\leqslant n$。 Translated by Eason_AC 2022.1.7

题目描述

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.

输入输出格式

输入格式

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

输出格式

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.

输入输出样例

输入样例 #1

3
2
1 2
10
3
3 1 2
111
8
2 3 1 8 5 4 7 6
01110001

输出样例 #1

2 1
3 1 2
1 6 5 8 3 2 4 7

说明

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