题目内容

印刷车间要印一段条码。模板是长度为 $n$ 的小写字母串 $s$（下标从 1 开始），另有长度为 $n$ 的正整数印量数组 $a$。你必须把 $a$ 重排为 $a'$，然后从空串开始生成条码 $t$：第 $i$ 步在 $t$ 末尾连续印刷恰好 $a'_i$ 个字符 $s_i$。

车间要求最终条码 $t$ 的字典序尽可能小。多种重排方案可输出任意一种。

字典序比较：从左到右比较字符，先出现较小字符的串更小；若其中一个是另一个的前缀，则较短者更小。

约束：测试组数不超过 10000；单组 $n$ 不超过 200000，且所有测试的 $n$ 之和不超过 200000；$a_i$ 不超过 1000000000。

输入描述

第一行一个整数 $T$，表示测试组数，满足 $1 \le T \le 10000$。 每组数据共三行：第一行整数 $n$（$1 \le n \le 200000$）；第二行长度为 $n$ 的小写字母串 $s$；第三行 $n$ 个整数 $a_1,\ldots,a_n$（$1 \le a_i \le 1000000000$）。保证单个文件中所有 $n$ 之和不超过 200000。

输出描述

对每组数据输出一行 $n$ 个整数，表示使 $t$ 字典序最小的一种重排。多解输出任意一种即可。

样例1

输入

2
4
dcba
9 3 1 6
4
xyyx
2 8 5 4

输出

1 3 6 9
8 2 4 5

说明

第一组串 dcba 各位后缀递减，应尽快进入更优后缀，因此从小到大分配，得到 1 3 6 9。 第二组串 xyyx 按相邻后缀排名取当前最大或最小，得到 8 2 4 5。

样例2

输入

1
6
zzxyyx
3 1 4 1 5 9

输出

1 1 9 3 4 5

说明

先对数组排序，再用后缀排名决定每个位置取当前最大还是最小，使拼接串字典序最小。

样例3

输入

1
3
mno
7 7 2

输出

7 7 2

说明

串 mno 严格递增，靠前位置应尽量多放，因此较大的 7 会优先分给更靠前且后缀更优的位置。