题目描述

给定一个长度为 $N$ 的字符串 $S$，由字符 A、B、C 组成。你可以对 $S$ 进行以下两种操作任意次数：

1. 选择 $S$ 中的一个 A，删除它，并在该位置插入 BB。

2. 选择 $S$ 中相邻的两个 B，删除它们，并在该位置插入 A。

请找出通过这些操作可以得到的字典序最小的字符串。

输入格式

输入$N$和$S$。

输出格式

输出所求答案。

样例

4
CBAA

CAAB

1
A

A

6
BBBCBB

ABCA

样例解释

【样例1说明】
我们应该进行以下操作：

• 初始时，S = CBAA。
• 删除第 3 个字符 A 并插入 BB，得到 S = CBBBA。
• 删除第 2 和第 3 个字符 BB 并插入 A，得到 S = CABA。
• 删除第 4 个字符 A 并插入 BB，得到 S = CABBB。
• 删除第 3 和第 4 个字符 BB 并插入 A，得到 S = CAAB。

我们无法得到字典序比 CAAB 更小的字符串。因此，答案是 CAAB。
【样例2说明】
我们不进行任何操作。

数据范围

• $1 \leq N \leq 200000$
• $S$ 是一个长度为 $N$ 的字符串，仅由 A、B、C 组成。

来源

• AtCoder ARC136A