题目描述

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$ 表示他喜欢第 $i$ 首歌。

现在，服务需要重新评估这些歌曲的评分，使得：

• 新的评分 $q_1, q_2, \dots, q_n$ 仍然构成一个排列（$1 \le q_i \le n$，每个整数 $1$ 到 $n$ 恰好出现一次）；
• Monocarp 喜欢的每首歌的评分都要高于他不喜欢的每首歌（形式化地说，对于所有满足 $s_i=1$ 且 $s_j=0$ 的 $i, j$，都应有 $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$），表示预测评分的排列。

第三行包含一个长度为 $n$ 的字符串 $s$，每个字符为 $0$ 或 $1$。$0$ 表示 Monocarp 不喜欢该歌曲，$1$ 表示喜欢。

所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一行 $n$ 个整数，表示重新评估后的歌曲评分排列 $q$。如果有多个使 $\sum\limits_{i=1}^n |p_i-q_i|$ 最小的答案，可以输出任意一个。

说明/提示

在第一个测试用例中，只有一种排列 $q$ 能满足所有喜欢的歌评分高于所有不喜欢的歌：第 $1$ 首歌评分为 $2$，第 $2$ 首歌评分为 $1$。$\sum\limits_{i=1}^n |p_i-q_i|=|1-2|+|2-1|=2$。

在第二个测试用例中，Monocarp 喜欢所有歌曲，因此所有排列都可以。使绝对差之和最小的排列是 $p$ 本身，其代价为 $0$。

由 ChatGPT 4.1 翻译

样例

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

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