#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
/*⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣤⠀⠀⠀⠀⠀⠀⠀⡄⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣤⣿⠛⣿⠀⠀⠀⠀⣤⣿⢻⡇⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣤⣿⡛⠀⣤⣿⣿⣤⣤⣿⣿⣤⢸⡇⠀
⠀⠀⠀⠀⠀⠀⠀⠀⣴⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⠀
⠀⠀⠀⠀⠀⠀⠀⣶⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡗⠀
⢠⣼⣿⣿⣿⣿⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷
⢸⣿⣿⡟⠛⠛⢿⣿⣿⣿⣿⣿⣿⣿⣤⣤⣤⣿⣿⣿⣿⣤⣤⣼⣿⣿
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠛⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⠋
*/
#define fi first
#define se second
#define pb push_back
#define ins insert
#define sz(a) (int)(a.size())
#define all(x) (x).begin(),(x).end()
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
#define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
#include "debug.h"
#else
#define debug(...)
#endif
//const int mod = 1e9+7;
//const int mod = 998244353;
const int MAXN=2e5+5;
const ll inf=1e9,INF=1e18;
int N;
vector<vector<vi>> pref;
vector<vi> pA,pB;
int encode(char c) {
if(c == 'A') return 0;
if(c == 'T') return 1;
return 2;
}
void init(string a, string b) {
N = a.size(); pref = vector<vector<vi>>(N+1,vector<vi>(3,vi(3,0))); pA = pB = vector<vi>(N+1,vi(3,0));
for(int i=1;i<=N;i++) {
for(int j=0;j<3;j++) {
pA[i][j] = pA[i-1][j]; pB[i][j] = pB[i-1][j];
for(int k=0;k<3;k++) {
pref[i][j][k] = pref[i-1][j][k];
}
} pref[i][encode(a[i-1])][encode(b[i-1])]++; pA[i][encode(a[i-1])]++; pB[i][encode(b[i-1])]++;
}
}
int get_distance(int x, int y) {
int amount[3][3]; bool f = 1;
for(int i=0;i<3;i++) {
f &= ((pA[y+1][i] - pA[x][i]) == (pB[y+1][i] - pB[x][i]));
for(int j=0;j<3;j++) {
amount[i][j] = pref[y+1][i][j] - pref[x][i][j];
}
} int ans = 0;
if(!f) return -1;
for(int i=0;i<3;i++) {
for(int j=0;j<3;j++) {
if(i == j) continue;
int mn = min(amount[i][j],amount[j][i]);
ans += mn;
amount[i][j] -= mn;
amount[j][i] -= mn;
}
}
int mx = 0;
for(int i=0;i<3;i++) {
for(int j=0;j<3;j++) {
if(i == j) continue;
mx = max(mx,amount[i][j]);
}
} ans += 2*mx;
return ans;
}
