分数: 400 点
问题陈述
对于字符串 T=T_1T_2\dots T_n 长度 n\ (2\leq n) 组成 A 和 B,我们定义一个字符串 f(T) 长度 n-1 如下。
- 让 a_1 < a_2 < \dots < a_{m} 是索引 i\ (1\leq i \leq n-1) 这样 T_i={}
A,和 b_1 < b_2 < \dots < b_k 是索引 i\ (1\leq i \leq n-1) 这样 T_i={}B。然后,让 f(T)=T_{a_1+1}T_{a_2+1}\dots T_{a_m+1}T_{b_1+1}T_{b_2+1}\dots T_{b_k+1}.
例如,对于字符串 T={}ABBABA,索引 i\ (1\leq i \leq 5) 与 T_i={}A 是 i=1,4,以及索引 i\ (1\leq i \leq 5) 与 T_i={}B 是 i=2,3,5,所以 f(T) is T_{1+1}T_{4+1}T_{2+1}T_{3+1}T_{5+1}={}BBBAA.
给你一个字符串 S 长度 N 组成 A 和 B.
查找 S 更换后 S 与 f(S) (N-1) 次。
你有 T 测试用例解决。
约束
- 1 \leq T \leq 10^5
- 2 \leq N \leq 3 \times 10^5
- S 是一个长度为 N 组成
A和B. - 输入中的所有数字均为整数。
- 总和 N 单个输入文件中的测试用例最多 3 \times 10^5.
输入
输入由标准输入按以下格式给出:
T
\mathrm{case}_1
\vdots
\mathrm{case}_T
每个案例均按以下格式给出:
N S
输出
打印 T 行。的 i- 第行应包含以下问题的答案 i- 第一个测试用例。
示例输入 1
3 2 AB 3 AAA 4 ABAB
示例输出 1
B A A
在第一个测试用例中, S 更改为 AB{}\rightarrow {}B.
在第二个测试用例中, S 更改为 AAA{} \rightarrow {}AA{} \rightarrow {}A.
在第三个测试用例中, S 更改为 ABAB{}\rightarrow {}BBA{} \rightarrow {}BA{} \rightarrow {}A.