#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define ull unsigned long long
#define pb push_back
#define fi first
#define sc second
#define vi vector<int>
#define pii pair<int,int>
#define vpi vector<pair<int,int> >
#define mp make_pair
const ll MOD1 = 1e9+7;
const ll MOD2 = 998244353;
const ll MOD3 = 1e9+93;
const ll MOD4 = 1e9+97;
const int INF = 1e9+7;
const int BASE = 1<<20;
const int LOG = 20;
const int ALF = 27;
const int MAXN = 1e6+7;
const int MAXNN = 1e3+7;
int p1[3][MAXN], p2[3][MAXN], m[6][MAXN];
void init(string a,string b){
a="%"+a, b="%"+b;
for(int i=1;i<a.size();i++){
for(int j=0;j<3;j++) p1[j][i]=p1[j][i-1];
if(a[i]=='A') p1[0][i]++;
else if(a[i]=='C') p1[1][i]++;
else p1[2][i]++;
}
for(int i=1;i<b.size();i++){
for(int j=0;j<3;j++) p2[j][i]=p2[j][i-1];
if(b[i]=='A') p2[0][i]++;
else if(b[i]=='C') p2[1][i]++;
else p2[2][i]++;
}
for(int i=1;i<a.size();i++){
for(int j=0;j<6;j++) m[j][i]=m[j][i-1];
if(a[i]=='A' and b[i]=='T') m[0][i]++;
if(a[i]=='T' and b[i]=='A') m[1][i]++;
if(a[i]=='C' and b[i]=='A') m[2][i]++;
if(a[i]=='A' and b[i]=='C') m[3][i]++;
if(a[i]=='T' and b[i]=='C') m[4][i]++;
if(a[i]=='C' and b[i]=='T') m[5][i]++;
}
}
int get_distance(int x,int y){
x++, y++;
int x1,x2,x3,x4,x5,x6,x7,x8,x9;
for(int i=0;i<3;i++) if(p1[i][y]-p1[i][x-1]!=p2[i][y]-p2[i][x-1]) return -1;
x1=m[0][y]-m[0][x-1];
x2=m[1][y]-m[1][x-1];
x3=m[2][y]-m[2][x-1];
x4=m[3][y]-m[3][x-1];
x5=m[4][y]-m[4][x-1];
x6=m[5][y]-m[5][x-1];
x7=max(x1,x2)-min(x1,x2);
x8=max(x3,x4)-min(x3,x4);
x9=max(x5,x6)-min(x5,x6);
return min(x1,x2)+min(x3,x4)+min(x5,x6)+(2*(x7+x8+x9)/3);
}
