← 返回题目列表

Codeforces · 1622/B

B. 贝兰德音乐

中文机器翻译题面 查看原题

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