题目描述
A
,B
のみからなる長さ n (2≤ n) の文字列 T=T1T2… Tn に対し、長さ n−1 の文字列 f(T) を以下のように定めます。
- Ti=
A
が成り立つ i (1≤ i ≤ n−1) 全体を a1 < a2 < … < am とし、 Ti=B
が成り立つ i (1≤ i ≤ n−1) 全体を b1 < b2 < … < bk とする。このとき、 $ 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
について、Ti=A
が成り立つ i (1≤ i ≤ 5) 全体は i=1,4 , Ti=B
が成り立つ i (1≤ i ≤ 5) 全体は i=2,3,5 であるため、f(T) は T1+1T4+1T2+1T3+1T5+1=BBBAA
になります。
A
,B
のみからなる長さ N の文字列 S が与えられます。
S を f(S) で置き換えることを N−1 回行った後の S を求めてください。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
输入格式
入力は以下の形式で標準入力から与えられます。
T case1 ⋮ caseT
各ケースは以下の形式で与えられます。
N S
输出格式
T 行出力してください。i 行目には i 番目のテストケースに対する答えを出力してください。
题目大意
对于一个长为 n≥2 的只由 A
和 B
组成的字符串 S[1…n],定义 f(S) 是 S 中从左到右所有 A
右边的第一个字符组成的字符串加上 S 中从左到右所有 B
右边的第一个字符组成的字符串。由于 S 中除了最右边的字符之外右边都有字符,所以 f(S) 的长度为 n−1。
T 组数据,给出 S,将 S 反复执行 S→f(S) 直到 S 长度为 1,问你最后的这个字符是 A
还是 B
。
- ∑n≤3×105
3
2
AB
3
AAA
4
ABAB
B
A
A
提示
制約
- 1 ≤ T ≤ 105
- 2 ≤ N ≤ 3 × 105
- S は
A
,B
のみからなる長さ N の文字列
- 入力される数値はすべて整数
- 1 つの入力に含まれるテストケースについて、 N の総和は 3 × 105 以下
Sample Explanation 1
1 つ目のテストケースについて、S は AB
→ B
と変化します。 2 つ目のテストケースについて、S は AAA
→ AA
→ A
と変化します。 3 つ目のテストケースについて、S は ABAB
→ BBA
→ BA
→ A
と変化します。