配点 : $300$ 点

問題文

A, B, C からなる長さ $N$ の文字列 $S$ が与えられます．

あなたは，$S$ に対して以下の $2$ 種類の操作を好きな順序で好きな回数行うことができます．

• $S$ の中で A を選び，消す． 文字を消した位置に，新たに BB を書き込む．
• $S$ の中で隣接する $2$ 文字であって，BB となっているものを選び，消す． 文字を消した位置に，新たに A を書き込む．

操作を終えたあとの $S$ としてあり得る文字列のうち，辞書順最小のものを求めてください．

制約

• $1 \leq N \leq 200000$
• $S$ は A, B, C からなる長さ $N$ の文字列

入力

入力は以下の形式で標準入力から与えられる．

$N$

$S$

出力

答えを出力せよ．

4
CBAA

CAAB

以下のように操作すればよいです．

• 最初，$S=$CBAA である．
• $S$ の $3$ 文字目の A を消し，BB を書き込む．$S=$CBBBA となる．
• $S$ の $2,3$ 文字目の BB を消し，A を書き込む．$S=$CABA となる．
• $S$ の $4$ 文字目の A を消し，BB を書き込む．$S=$CABBB となる．
• $S$ の $3,4$ 文字目の BB を消し，A を書き込む．$S=$CAAB となる．

$S$ を CAAB より辞書順で小さい文字列にすることはできません． よって答えは CAAB になります．

1
A

A

一度も操作を行いません．

6
BBBCBB

ABCA