#include <bits/stdc++.h>
#include "dna.h"
#include <cstdio>
#include <cassert>
#include <string>
#include <vector>
using namespace std;
vector <int> poza[5],pozb[5];
int n,sum[100005],val[505];
int caterinca[100005][4][4];
void init (string a,string b)
{
n=a.size();
val['A']=1;
val['T']=2;
val['C']=3;
for (int i=0; i<a.size(); i++)
{
if (i==0)
{
sum[i]=(a[i]!=b[i]);
}
else
{
sum[i]=sum[i-1]+(a[i]!=b[i]);
}
if (i>0)
{
for (int t=1; t<=3; t++)
{
for (int k=1; k<=3; k++)
{
caterinca[i][t][k]=caterinca[i-1][t][k];
}
}
}
caterinca[i][val[a[i]]][val[b[i]]]++;
poza[val[a[i]]].push_back(i);
pozb[val[b[i]]].push_back(i);
}
}
int cautsta(int loc,int poz)
{
int st=0,dr=(int)poza[loc].size()-1,mij;
int sol=poza[loc].size();
while (st<=dr)
{
mij=(st+dr)/2;
if (poza[loc][mij]>=poz)
{
sol=mij;
dr=mij-1;
}
else
{
st=mij+1;
}
}
return sol;
}
int cautstb(int loc,int poz)
{
int st=0,dr=(int)pozb[loc].size()-1,mij;
int sol=pozb[loc].size();
while (st<=dr)
{
mij=(st+dr)/2;
if (pozb[loc][mij]>=poz)
{
sol=mij;
dr=mij-1;
}
else
{
st=mij+1;
}
}
return sol;
}
int cautdra(int loc,int poz)
{
int st=0,dr=(int)poza[loc].size()-1,mij;
int sol=-1;
while (st<=dr)
{
mij=(st+dr)/2;
if (poza[loc][mij]<=poz)
{
sol=mij;
st=mij+1;
}
else
{
dr=mij-1;
}
}
return sol;
}
int cautdrb(int loc,int poz)
{
int st=0,dr=(int)pozb[loc].size()-1,mij;
int sol=-1;
while (st<=dr)
{
mij=(st+dr)/2;
if (pozb[loc][mij]<=poz)
{
sol=mij;
st=mij+1;
}
else
{
dr=mij-1;
}
}
return sol;
}
int get_distance(int x,int y)
{
for (int i=1; i<=3; i++)
{
int sta,stb,dra,drb;
sta=cautsta(i,x);
stb=cautstb(i,x);
dra=cautdra(i,y);
drb=cautdrb(i,y);
if (dra-sta!=drb-stb)
{
return -1;
}
}
int bonjour[4][4],sum=0,i,j;
for (i=1; i<=3; i++)
{
for (j=1; j<=3; j++)
{
if (i!=j)
{
if (x==0)
{
bonjour[i][j]=caterinca[y][i][j];
bonjour[j][i]=caterinca[y][j][i];
}
else
{
bonjour[i][j]=caterinca[y][i][j]-caterinca[x-1][i][j];
bonjour[j][i]=caterinca[y][j][i]-caterinca[x-1][j][i];
}
}
}
}
for (i=1;i<=3;i++)
{
for (j=1;j<=3;j++)
{
if (i!=j)
{
int val=min(bonjour[i][j],bonjour[j][i]);
sum=sum+val;
bonjour[i][j]-=val;
bonjour[j][i]-=val;
}
}
}
int ok=0,sum2=0;
for (i=1;i<=3;i++)
{
for (j=1;j<=3;j++)
{
if (i!=j&&bonjour[i][j]!=0)
{
sum2=sum2+bonjour[i][j];
}
}
}
sum=sum+2*sum2/3;
return sum;
}
/*int main() {
int n, q;
assert(scanf("%d %d", &n, &q) == 2);
char A[n+1], B[n+1];
assert(scanf("%s", A) == 1);
assert(scanf("%s", B) == 1);
std::string a = std::string(A);
std::string b = std::string(B);
std::vector<int> x(q), y(q);
for (int i = 0; i < q; i++) {
assert(scanf("%d %d", &x[i], &y[i]) == 2);
}
fclose(stdin);
std::vector<int> results(q);
init(a, b);
for (int i = 0; i < q; i++) {
results[i] = get_distance(x[i], y[i]);
}
for (int i = 0; i < q; i++) {
printf("%d\n", results[i]);
}
fclose(stdout);
return 0;
}*/
