#include "dna.h"
#include "bits/stdc++.h"
using namespace std;
int pa[3][100001];
int pb[3][100001];
int cc[6][100001];
void init(string a,string b)
{
int n=a.size();
pa[0][0]=(a[0]=='A');
pa[1][0]=(a[0]=='C');
pa[2][0]=(a[0]=='T');
for(int i=1;i<n;i++)
{
pa[0][i]=pa[0][i-1]+(a[i]=='A');
pa[1][i]=pa[1][i-1]+(a[i]=='C');
pa[2][i]=pa[2][i-1]+(a[i]=='T');
}
pb[0][0]=(b[0]=='A');
pb[1][0]=(b[0]=='C');
pb[2][0]=(b[0]=='T');
for(int i=1;i<n;i++)
{
pb[0][i]=pb[0][i-1]+(b[i]=='A');
pb[1][i]=pb[1][i-1]+(b[i]=='C');
pb[2][i]=pb[2][i-1]+(b[i]=='T');
}
cc[0][0]=(b[0]=='A'&&a[0]=='C');
cc[1][0]=(b[0]=='C'&&a[0]=='A');
cc[2][0]=(b[0]=='A'&&a[0]=='T');
cc[3][0]=(b[0]=='T'&&a[0]=='A');
cc[4][0]=(b[0]=='C'&&a[0]=='T');
cc[5][0]=(b[0]=='T'&&a[0]=='C');
for(int i=1;i<n;i++)
{
cc[0][i]=cc[0][i-1]+(b[i]=='A'&&a[i]=='C');
cc[1][i]=cc[1][i-1]+(b[i]=='C'&&a[i]=='A');
cc[2][i]=cc[2][i-1]+(b[i]=='A'&&a[i]=='T');
cc[3][i]=cc[3][i-1]+(b[i]=='T'&&a[i]=='A');
cc[4][i]=cc[4][i-1]+(b[i]=='C'&&a[i]=='T');
cc[5][i]=cc[5][i-1]+(b[i]=='T'&&a[i]=='C');
}
}
int get(int l,int r,int x,int t){
if(t==0){
if(l==0) return pa[x][r];
else return pa[x][r]-pa[x][l-1];
}
else{
if(l==0) return pb[x][r];
else return pb[x][r]-pb[x][l-1];
}
}
int cnt(int l,int r,int x){
if(l==0) return cc[x][r];
else return cc[x][r]-cc[x][l-1];
}
int get_distance(int x,int y)
{
vector<int>ca(3),cb(3);
ca[0]=get(x,y,0,0);
ca[1]=get(x,y,1,0);
ca[2]=get(x,y,2,0);
cb[0]=get(x,y,0,1);
cb[1]=get(x,y,1,1);
cb[2]=get(x,y,2,1);
for(int i=0;i<3;i++) if(ca[i]!=cb[i]) return -1;
int AC=cnt(x,y,0);
int CA=cnt(x,y,1);
int AT=cnt(x,y,2);
int TA=cnt(x,y,3);
int CT=cnt(x,y,4);
int TC=cnt(x,y,5);
int res=0;
int s1=min(AC,CA);
int s2=min(AT,TA);
int s3=min(CT,TC);
res+=s1;
res+=s2;
res+=s3;
AC-=s1;
CA-=s1;
AT-=s2;
TA-=s2;
CT-=s3;
TC-=s3;
int add=(AC+CA+AT+TA+CT+TC);
return (res+((add/3)*2));
}
