#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int pfa[N], pfc[N], pft[N], pfa1[N], pfc1[N], pft1[N], pfac[N], pfat[N], pfca[N], pfct[N], pfta[N], pftc[N];
void init(string a, string b){
for(int i = 1;i<=a.size();i++){
pfa[i] = pfa[i - 1]; pfc[i] = pfc[i - 1]; pft[i] = pft[i - 1]; pfa1[i] = pfa1[i - 1]; pfc1[i] = pfc1[i - 1]; pft1[i] = pft1[i - 1]; pfac[i] = pfac[i - 1]; pfat[i] = pfat[i - 1]; pfca[i] = pfca[i - 1]; pfct[i] = pfct[i - 1]; pfta[i] = pfta[i - 1]; pftc[i] = pftc[i - 1];
if(b[i - 1] == 'A'){
pfa[i]++;
if(a[i - 1] == 'A'){
pfa1[i]++;
}else if(a[i - 1] == 'C'){
pfc1[i]++; pfca[i]++;
}else{
pft1[i]++; pfta[i]++;
}
}else if(b[i - 1] == 'C'){
pfc[i]++;
if(a[i - 1] == 'A'){
pfa1[i]++; pfac[i]++;
}else if(a[i - 1] == 'C'){
pfc1[i]++;
}else{
pft1[i]++; pftc[i]++;
}
}else{
pft[i]++;
if(a[i - 1] == 'A'){
pfa1[i]++; pfat[i]++;
}else if(a[i - 1] == 'C'){
pfc1[i]++; pfct[i]++;
}else{
pft1[i]++;
}
}
}
}
int get_distance(int x, int y){
++x; ++y;
if(pfa[y] - pfa[x - 1] != pfa1[y] - pfa1[x - 1] || pfc[y] - pfc[x - 1] != pfc1[y] - pfc1[x - 1] || pft[y] - pft[x - 1] != pft1[y] - pft1[x - 1]) return -1;
int ac = pfac[y] - pfac[x - 1], at = pfat[y] - pfat[x - 1], ca = pfca[y] - pfca[x - 1], ct = pfct[y] - pfct[x - 1], ta = pfta[y] - pfta[x - 1], tc = pftc[y] - pftc[x - 1];
int mac = min(ac, ca), lac = max(ac, ca) - mac;
int mat = min(at, ta), lat = max(at, ta) - mat;
int mct = min(ct, tc), lct = max(ct, tc) - mct;
return mac + mat + mct + min({lac + lat, lac + lct, lat + lct});
}
