基因

题目描述

仅由 $\mathbb{A}, \mathbb{T}, \mathbb{C}, \mathbb{G}$ 四个大写字母构成的一个字符串称作基因序列。对于一个基因序列，基因位段突变形式为 $\theta$ 。

首先，对于单位字符，有 $\theta( \mathtt{A} )=\mathtt{T}, \theta( \mathtt{T} )=\mathtt{A}, \theta( \mathtt{C} )=\mathtt{G}, \theta( \mathtt{G} )=\mathtt{C}$。

其次，对于长为 $n$ 的字符串 $x$与$1 \leq i \leq j \leq n$ ，$\theta( i, j )$ 是使用 $\theta( x_{j} ) \theta( x_{j-1} ) \cdots\theta( x_{i} )$ 替代 $x$ 的第 $i$ 至 $j$ 个字符，即先反序排列区间中字符，然后逐个应用单字符修改。

现有一个长度为 $n$ 的基因序列 $X$，求一种选取 $1 \leq i \leq j \leq n$ 的方式，使得 $X$ 执行 $\theta( i, j )$ 后字典序最小。注意操作对原始字符串仅执行恰好一次，不能不操作。

输入格式

输入一行，一个由 $\mathbb{A}, \mathbb{T}, \mathbb{C}, \mathbb{G}$ 构成的字符串 $X,$ 表示基因序列。其长度记为 $n$。

输出格式

输出一行，一个长度为 $n$ 的字符串，表示 $X$ 执行某种$\theta( i, j )$ 后所有可能结果中，字典序最小的一个。

样例 1

ACGTACGT

AACGACGT

样例一解释

执行 $\theta( 2, 4 )$ 。

数据说明

共20个测试点。

对$20\%$数据保证 $n \leq5 0 0$ ;

对$5 0 \%$数据保证 $n \leq5 0 0 0$ ;

对$7 0 \%$ 数据保证 $n \leq 50 0 0 0$ ;

对$100\%$数据保证 $n \leq 500000$。

下发大样例ex_A1到ex_A4依次符合4种数据范围的要求。

更多样例

以下 4 组大样例取自原题附件：

• ex_A1.in / ex_A1.out
• ex_A2.in / ex_A2.out
• ex_A3.in / ex_A3.out
• ex_A4.in / ex_A4.out