解题思路

设重排后的数组为 $a'$，最终得到的字符串为：

$t = s_1^{a'_1} + s_2^{a'_2} + \cdots + s_n^{a'_n}$

其中 $s_i^{a'_i}$ 表示把字符 $s_i$ 重复 $a'_i$ 次。

题目要求重排数组 $a$，让字符串 $t$ 的字典序最小。

题目内容

游游有一个长度为 $n$ 的字符串 $s$ (下标从 $1$ 开始，且仅由小写字母构成)，以及一个长度为n的数组 {$a_1,a_2,...,a_n$} 游游希望你对数组进行重排。随后，游游将使用重排后的数组(记重排后的数组为 $a'$)，按照 $1$ ~ $n$ 的顺序，从空串开始拼接生成一个新的字符串 $t$ :

• 第 $i$ 次操作在 $t$ 的末尾拼接 $a'$ 个 $s_i$ 。

游游希望最终得到的字符串 $t$ 的字典序尽可能小。请你输出使得 $t$ 的字典序最小化时，重排后的数组，如果有多个答案你可以输出任意一种。

【名词解释】

重排：将数组中的元素以任意顺序重新排列，得到与原数组长度相同、元素集合相同的新数组。

字符串的字典序比较：从左到右逐个比较两个字符串的字符。如果在某个位置上字符不同，比较这两个字符的$ASCII$ 码顺序，$ASCll$ 码小的字符串字典序也小。如果一直比较到其中一个字符串结束，则较短的字符串字典序更小。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1≤T≤10^4)$ 代表数据组数，每组测试数据描述如下：

第一行输入一个整数 $n(1≤n≤2×10^5)$ 表示字符串与数组的长度；

第二行输入一个长度为 $n$ 、仅由小写字母构成的字符串 $s$ ；

第三行输入 $n$ 个整数 $a_1,a_2,...,a_n(1≤a_i≤10^9)$ 表示数组元素。

除此之外，保证单个测试文件的 $n$ 之和不超过 $2×10^5$ 。

输出描述

对于每一组测试数据，新起一行，输出 $n$ 个整数，表示使字符串 $t$ 字典序最小化时重排后的数组。

如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

样例1

输入

2
5
aabcd
1 2 3 4 5
3
bac
1 1 2

输出

4 5 3 2 1
1 2 1

说明

在第一个样例中拼接得到的字符串 $t$ 为 "$aaaaaaaaabbbccd$"，第二个样例中拼接得到的字符串 $t$ 为 "$baac$" 可以证明不存在更好的拼接方式。