/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
A,B のみからなる長さ n\ (2\leq n) の文字列 T=T_1T_2\dots T_n に対し、長さ n-1 の文字列 f(T) を以下のように定めます。
- T_i={}
Aが成り立つ i\ (1\leq i \leq n-1) 全体を a_1 < a_2 < \dots < a_{m} とし、 T_i={}Bが成り立つ i\ (1\leq i \leq n-1) 全体を b_1 < b_2 < \dots < b_k とする。このとき、 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 について、T_i={}A が成り立つ i\ (1\leq i \leq 5) 全体は i=1,4 , T_i={}B が成り立つ i\ (1\leq i \leq 5) 全体は i=2,3,5 であるため、f(T) は T_{1+1}T_{4+1}T_{2+1}T_{3+1}T_{5+1}={}BBBAA になります。
A,B のみからなる長さ N の文字列 S が与えられます。
S を f(S) で置き換えることを N-1 回行った後の S を求めてください。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 1 \leq T \leq 10^5
- 2 \leq N \leq 3 \times 10^5
- S は
A,Bのみからなる長さ N の文字列 - 入力される数値はすべて整数
- 1 つの入力に含まれるテストケースについて、 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
1 つ目のテストケースについて、S は AB{}\rightarrow {}B と変化します。
2 つ目のテストケースについて、S は AAA{} \rightarrow {}AA{} \rightarrow {}A と変化します。
3 つ目のテストケースについて、S は ABAB{}\rightarrow {}BBA{} \rightarrow {}BA{} \rightarrow {}A と変化します。
Score : 400 points
Problem Statement
For a string T=T_1T_2\dots T_n of length n\ (2\leq n) consisting of A and B, we define a string f(T) of length n-1 as follows.
- Let a_1 < a_2 < \dots < a_{m} be the indices i\ (1\leq i \leq n-1) such that T_i={}
A, and b_1 < b_2 < \dots < b_k be the indices i\ (1\leq i \leq n-1) such that T_i={}B. Then, let 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}.
For example, for the string T={}ABBABA, the indices i\ (1\leq i \leq 5) with T_i={}A are i=1,4, and the indices i\ (1\leq i \leq 5) with T_i={}B are i=2,3,5, so f(T) is T_{1+1}T_{4+1}T_{2+1}T_{3+1}T_{5+1}={}BBBAA.
You are given a string S of length N consisting of A and B.
Find S after replacing S with f(S) (N-1) times.
You have T test cases to solve.
Constraints
- 1 \leq T \leq 10^5
- 2 \leq N \leq 3 \times 10^5
- S is a string of length N consisting of
AandB. - All numbers in the input are integers.
- The sum of N over the test cases in a single input file is at most 3 \times 10^5.
Input
The input is given from Standard Input in the following format:
T
\mathrm{case}_1
\vdots
\mathrm{case}_T
Each case is given in the following format:
N S
Output
Print T lines. The i-th line should contain the answer to the i-th test case.
Sample Input 1
3 2 AB 3 AAA 4 ABAB
Sample Output 1
B A A
In the first test case, S changes as AB{}\rightarrow {}B.
In the second test case, S changes as AAA{} \rightarrow {}AA{} \rightarrow {}A.
In the third test case, S changes as ABAB{}\rightarrow {}BBA{} \rightarrow {}BA{} \rightarrow {}A.