首先枚举确定最优解中从左往右第一个有变化的字符，然后对从它开始的后缀 $S_0$ 施加 $f$ 操作并翻转得到 $T_0$，问题就变成了求 $T_0$ 的最小字典序后缀，直接上 SA 即可。

#include <bits/stdc++.h>
using namespace std;
char cv(char x)
{
    switch(x)
    {
        case 'A': return 'T';
        case 'C': return 'G';
        case 'G': return 'C';
        case 'T': return 'A';
    }
}
int fw(int x, int y, int z)
{
    if (x - y >= z) return x - y;
    return - y - z;
}
int go(string s)
{
    int n = s.size();
    s = ' ' + s;
    char c = ' ';
    for (int i = 1; i <= n; i++)
        c = max(c, s[i]);
    int g = 1;
    while (g <= n && s[g] <= cv(c)) g++;
    if (g > n)
    {
        s[n] = cv(s[n]);
        s.erase(0, 1);
        cout << s << '\n';
        return 0;
    }
    deque <int> q;
    for (int i = n; i >= g; i--)
        if (s[i] == c) q.push_back(i);
    int r = 0;
    while (q.size() > 1)
    {
        char c = ' ';
        int k = q.size();
        while (k--)
        {
            int u = q.front();
            q.pop_front();
            q.push_back(u);
            int v = fw(u, r, g);
            if (v < 0) c = max(c, cv(s[-v]));
            else c = max(c, s[v]);
        }
        k = q.size();
        while (k--)
        {
            int u = q.front();
            q.pop_front();
            int v = fw(u, r, g);
            char d;
            if (v > 0) d = s[v];
            else d = cv(s[-v]);
            if (d == c) q.push_back(u);
        }
        k = q.size();
        while (k--)
        {
            int u = q.back();
            q.pop_back();
            if (!k)
            {
                q.push_front(u);
                break;
            }
            int w = q.back();
            int v = fw(w, r, g);
            if (v > u) q.push_front(u);
        }
        r++;
    }
    int f = q.front();
    string t = s.substr(g, f - g + 1);
    reverse(t.begin(), t.end());
    s.replace(g, f - g + 1, t);
    for (int i = g; i <= f; i++)
        s[i] = cv(s[i]);
    s.erase(0, 1);
    cout << s << '\n';
    return 0;
}
int main()
{
    ios::sync_with_stdio(0);
    string s;
    while (cin >> s) go(s);
    return 0;
}