#include<bits/stdc++.h>
#include<iostream>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define vi vector<int>
#define mii map<int,int>
#define pqb priority_queue<int>
#define pqs priority_queue<int,vi,greater<int> >
#define mod 1000000007
#define inf 1e18
#define rep(x,s,e) for (auto x=s-(s>e);x!=e-(s>e);s<e?x++:x--)
#define w(x) int x; cin>>x; while(x--)
string a,b;
int n;
vector<int> cnta[3], cntb[3]; // A,T,C
vector<int> trans[6]; // AT,TA,AC,CA,TC,CT
const int A=0, T=1, C=2;
unordered_map<char,int> m = {{'A',A},{'T',T},{'C',C}};
void init(string X, string Y) {
n=X.size();
a=X, b=Y;
for(int i=0;i<3;i++){ cnta[i].assign(n, 0); cntb[i].assign(n, 0); }
for(int i=0;i<6;i++) trans[i].assign(n, 0);
int c1,c2;
for(int i=0;i<n;i++){
c1 = m[X[i]]; c2 = m[Y[i]];
cnta[c1][i] = 1;
cntb[c2][i] = 1;
if(c1==0 && c2==1) trans[0][i]++;
else if(c1==1 && c2==0) trans[1][i]++;
else if(c1==0 && c2==2) trans[2][i]++;
else if(c1==2 && c2==0) trans[3][i]++;
else if(c1==1 && c2==2) trans[4][i]++;
else if(c1==2 && c2==1) trans[5][i]++;
}
// prefix sum
for(int i=1;i<n;i++){
for(int j=0;j<3;j++){
cnta[j][i] += cnta[j][i-1];
cntb[j][i] += cntb[j][i-1];
}
for(int j=0;j<6;j++){
trans[j][i] += trans[j][i-1];
}
}
}
int get_distance(int x, int y) {
for(int i=0;i<3;i++){
if(cnta[i][y] - (x==0?0:cnta[i][x-1]) != cntb[i][y] - (x==0?0:cntb[i][x-1])) return -1;
}
int cnt = 0;
int q[6];
for(int i=0;i<6;i++) q[i] = trans[i][y] - (x==0?0:trans[i][x-1]);
cnt = min(q[0], q[1]) + min(q[2], q[3]) + min(q[4], q[5]);
cnt += abs(q[0] - q[1])*2;
return cnt;
}
