小睿想为自己的女朋友制作一个非常美丽的字母珍珠项链，他现在手中有一个字母项链的雏形，每一颗珍珠上刻有字符A或者字符B，他想要添加一些珍珠将其完善成最美的状态，小睿认为最美的字母项链应该满足：当项链被解开时，由珍珠构成的仅包含A和B的字符串符合“最美序列”的要求。

其中“最美序列”定义如下：

• 空串时是一个最美序列
• 如果s是最美序列，那么AsB也是一个最美序列
• 如果s和t都是最美序列，那么st也是最美序列

例如，"AABBAB", "AB", "AABABBAB" 都是最美序列，而，"BA", "AAB", "AABBBA"不是最美序列。由于珍珠非常贵，小睿想要加最少的珍珠将项链完善成最美的状态。珍珠项链可以在任意位置解开，故只要存在一种解开方式，使得得到的字符串符合“最美序列”的要求便认为此时项链已经达到最美状态。

输出该解开后的字符串，如果存在多种情况，输出字典序最小的。

输入输出格式

输入格式：

• 输入包含一行一个字符串，表示小睿的珍珠字母项链雏形，字符串仅包含字符"A"与字符"B"。

输出格式：

• 输出一行为小睿完善后的项链解开后得到的字符串，如果存在多种情况，输出字典序最小的。

输入输出样例

输入样例1:

ABAABB

输出样例1:

AABBAB

样例说明1:

该项链本身不需额外添加珍珠，但需要输出字典序最小的情况，即将环形项链旋转2位，得到AABBAB

输入样例2:

ABA

输出样例2:

AABB

样例说明2:

该项链在B与A之间添加一个珍珠B，然后旋转后解开，得到AABB，满足最美序列

测试点

语言|C|C++|Python|JAVA -|-|-|-|- 每个测试点时限|2.0秒|2.0秒|5.0秒|5.0秒 内存限制|512MB|512MB|512MB|512MB 测试点数目|20|20|20|20 测试点是否等分|是|是|是|是

对于所有测试点，$1 \le$ 字符串长度 $\le 10^6$。