/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 1000 点
問題文
文字 A B のみからなる長さ N の文字列 S が与えられます.
文字 1 2 3 のみからなる長さ N の文字列 X に対して スコア を以下の手順によって定めます.
まず変数 h_1,h_2,h_3,P をそれぞれ 0 で初期化します.
次に i=1,2,\dots ,N の順に次の操作を行います.
S の i 文字目が
Aなら操作Aを,Bなら操作Bを行う. ただし, X の i 文字目が表す数字を d とする.
操作A : h_d に 2 を加算する.
操作B : d=2 または h_d\neq h_2 のとき P を -10^{100} とする. そうでなければ h_d と h_2 にそれぞれ 1 を加算する.
h_1=h_2=h_3 のとき P に 1 を加える.
最後に最終的な P をスコアとします.
スコアを最大にする X を 1 つ出力してください.
T 個のテストケースが与えられるので, それぞれについて解いてください.
制約
- 1\le T\le 10^5
- 1\le N\le 10^6
- S は
ABのみからなる長さ N の文字列 - T,N は整数
- すべてのテストケースにおける N の総和は 10^6 以下
入力
入力は以下の形式で標準入力から与えられる. ここで \mathrm{test}_i は i 番目のテストケースを意味する.
T
\mathrm{test}_1
\mathrm{test}_2
\vdots
\mathrm{test}_T
各テストケースは以下の形式で与えられる.
N S
出力
T 行出力せよ.
i\ (1\le i\le T) 行目には i 番目のテストケースにおけるスコアを最大にする文字列 X を 1 つ出力せよ.
なお, スコアを最大にする X が複数存在する場合は, どれを出力しても正答となる.
入力例 1
5 4 ABBA 5 AAAAA 6 BBBBBB 7 ABABABA 20 AAABBBBBBBBAAABBBABA
出力例 1
1333 12321 333333 1313212 33311111133121111311
手順で i=1,2,\dots ,N と進む際の (h_1,h_2,h_3,P) の変化を述べます.
- 1 番目のテストケースについて, (0,0,0,0)\rightarrow (2,0,0,0)\rightarrow (2,1,1,0)\rightarrow (2,2,2,1)\rightarrow (2,2,4,1) となります. スコアの最大値は 1 です.
- 2 番目のテストケースについて, (0,0,0,0)\rightarrow (2,0,0,0)\rightarrow (2,2,0,0)\rightarrow (2,2,2,1)\rightarrow (2,4,2,1)\rightarrow (4,4,2,1) となります. スコアの最大値は 1 です.
3,4,5 番目のテストケースでは, スコアの最大値はそれぞれ 0,0,2 です. スコアが最大となる X は複数存在する可能性がありますが, そのうちの 1 つを出力してください.
Score : 1000 points
Problem Statement
You are given a string S of length N consisting of the characters A and B.
For a string X of length N consisting of the characters 1, 2, and 3, the score is determined by the following procedure:
First, initialize the variables h_1, h_2, h_3, P to 0.
Then, for i = 1, 2, \dots, N in this order, perform the following operations:
If the i-th character of S is
A, perform operation A; if it isB, perform operation B. Let d be the number represented by the i-th character of X.
Operation A: Add 2 to h_d.
Operation B: If d = 2 or h_d \neq h_2, set P to -10^{100}. Otherwise, add 1 to both h_d and h_2.
If h_1 = h_2 = h_3, add 1 to P.
The final value of P is the score.
Print one string X that maximizes the score.
You have T test cases to solve.
Constraints
- 1 \leq T \leq 10^5
- 1 \leq N \leq 10^6
- S is a string of length N consisting of
AandB. - T and N are integers.
- The sum of N across all test cases is at most 10^6.
Input
The input is given from Standard Input in the following format. Here, \mathrm{test}_i denotes the i-th test case.
T
\mathrm{test}_1
\mathrm{test}_2
\vdots
\mathrm{test}_T
Each test case is given in the following format:
N S
Output
Print T lines.
The i-th line (1 \leq i \leq T) should contain a string X that maximizes the score for the i-th test case.
If multiple strings X maximize the score, any of them is considered correct.
Sample Input 1
5 4 ABBA 5 AAAAA 6 BBBBBB 7 ABABABA 20 AAABBBBBBBBAAABBBABA
Sample Output 1
1333 12321 333333 1313212 33311111133121111311
Let us describe the changes in (h_1, h_2, h_3, P) as we proceed with i = 1, 2, \dots, N.
- For the first test case, (0,0,0,0) \rightarrow (2,0,0,0) \rightarrow (2,1,1,0) \rightarrow (2,2,2,1) \rightarrow (2,2,4,1). The maximum score is 1.
- For the second test case, (0,0,0,0) \rightarrow (2,0,0,0) \rightarrow (2,2,0,0) \rightarrow (2,2,2,1) \rightarrow (2,4,2,1) \rightarrow (4,4,2,1). The maximum score is 1.
For the third, fourth, and fifth test cases, the maximum scores are 0, 0, and 2, respectively. There may be multiple strings X that maximize the score, but you only need to print one of them.