#include "dna.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std;
const int N=1e5+50;
int a[N],b[N],n,pref[N][4][3];
map<pair<int,int>,int>pmapa[N];
void init(std::string s, std::string t)
{
n=s.size();
for(int i=1;i<=n;i++)
{
if(s[i-1]==t[i-1])
{
a[i]=0,b[i]=0;
continue;
}
if(s[i-1]=='A') a[i]=1;
if(s[i-1]=='C') a[i]=2;
if(s[i-1]=='T') a[i]=3;
if(t[i-1]=='A') b[i]=1;
if(t[i-1]=='C') b[i]=2;
if(t[i-1]=='T') b[i]=3;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=3;j++)
{
for(int k=1;k<=2;k++)
{
pref[i][j][k]=pref[i-1][j][k];
}
}
pref[i][a[i]][1]++;
pref[i][b[i]][2]++;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=3;j++)
{
for(int k=1;k<=3;k++)
{
if(j==k)continue;
pmapa[i][{j,k}]=pmapa[i-1][{j,k}];
}
}
pmapa[i][{a[i],b[i]}]++;
//if(a[i]==b[j] && a[j]==b[i]) par.push_back({i,j});
}
}
int get_distance(int x, int y)
{
x++,y++;
int num[4][3],res=0;
for(int i=1;i<=3;i++)
{
for(int j=1;j<=2;j++)
{
num[i][j]=pref[y][i][j]-pref[x-1][i][j];
//printf("%i %i: %i\n",i,j,num[i][j]);
}
}
for(int i=1;i<=3;i++)
{
if(num[i][1]!=num[i][2]) return -1;
}
for(int i=1;i<=3;i++)
{
for(int j=i+1;j<=3;j++)
{
int a=pmapa[y][{i,j}]-pmapa[x-1][{i,j}],b=pmapa[y][{j,i}]-pmapa[x-1][{j,i}];
//printf("%i %i %i %i: %i %i\n",x,y,i,j,a,b);
a=min(a,b);
num[i][1]-=a;
num[j][1]-=a;
res+=a;
}
}
/*for(auto i:par)
{
if(x<=i.fi && i.se<=y)
{
num[a[i.fi]][1]--;
num[a[i.se]][1]--;
res++;
}
}*/
res+=num[1][1]+num[2][1]+num[3][1]-max(num[1][1],max(num[2][1],num[3][1]));
return res;
}
