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 喜欢的每首歌曲应该比 Monocarp 不喜欢的每首歌曲有更高的评分(正式来说,对于所有 $$$i, j$$$ 来说,$$$s_i=1$$$ 和 $$$s_j=0$$$,$$$q_i>q_j$$$ 应该成立)。
在所有有效排列 $$$q$$$ 中找到具有 $$$\sum\limits_{i=1}^n |p_i-q_i|$$$ 最小值的排列,其中 $$$|x|$$$ 是 $$$x$$$ 的绝对值。
打印排列 $$$q_1, q_2, \dots, q_n$$$。如果有多个答案,您可以打印其中任何一个。
输入
第一行包含一个整数 $$$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$$$) - 预测评分的排列。
第三行包含单个字符串 $$$s$$$,由 $$$n$$$ 个字符组成。每个字符要么是 $$$0$$$ 要么是 $$$1$$$。 $$$0$$$ 表示 Monocarp 不喜欢这首歌,$$$1$$$ 表示他喜欢这首歌。
所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个排列 $$$q$$$ — 重新评估的歌曲评级。如果有多个答案使得 $$$\sum\limits_{i=1}^n |p_i-q_i|$$$ 是可能的最小值,则可以打印其中任何一个。
示例
输入 #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
注意
在第一个测试用例中,仅存在一种排列 $$$q$$$,使得每首喜欢的歌曲的评级高于每首不喜欢的歌曲:歌曲 $$$1$$$ 获得评级 $$$2$$$ ,歌曲 $$$2$$$ 获得评级 $$$1$$$ 。 $$$\sum\limits_{i=1}^n |p_i-q_i|=|1-2|+|2-1|=2$$$。
在第二个测试用例中,Monocarp 喜欢所有歌曲,因此所有排列都可以工作。绝对差之和最小的排列是等于 $$$p$$$ 的排列。其成本为$$$0$$$。