#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX=1e9;
const int MAX_N=1e5+10;
int na[MAX_N][4],nb[MAX_N][4];
int gda[MAX_N][4],gdc[MAX_N][4],gdt[MAX_N][4];
int dif[MAX_N];
vector<int> da(3),dc(3),dt(3);
int n;
void init(std::string a, std::string b) {
memset(na,0,sizeof na);
memset(nb,0,sizeof nb);
memset(gda,0,sizeof gda); memset(gdc,0,sizeof gdc); memset(gdt,0,sizeof gdt);
memset(dif,0,sizeof dif);
n=a.size();
for(int i=0;i<n;i++){
if(i!=0){
for(int j=0;j<3;j++) na[i][j]=na[i-1][j];
for(int j=0;j<3;j++) nb[i][j]=nb[i-1][j];
}
if(a[i]=='A') na[i][0]++;
if(a[i]=='C') na[i][1]++;
if(a[i]=='T') na[i][2]++;
if(b[i]=='A') nb[i][0]++;
if(b[i]=='C') nb[i][1]++;
if(b[i]=='T') nb[i][2]++;
}
for(int i=0;i<n;i++){
if(i!=0){
dif[i]=dif[i-1];
for(int j=0;j<3;j++) gda[i][j]=gda[i-1][j];
for(int j=0;j<3;j++) gdc[i][j]=gdc[i-1][j];
for(int j=0;j<3;j++) gdt[i][j]=gdt[i-1][j];
}
if(a[i]!=b[i]) dif[i]++;
int id=0;
if(a[i]=='A') id=0;
if(a[i]=='C') id=1;
if(a[i]=='T') id=2;
if(b[i]=='A') gda[i][id]++;
if(b[i]=='C') gdc[i][id]++;
if(b[i]=='T') gdt[i][id]++;
}
}
int get_distance(int x, int y) {
int aa,ac,at,ba,bc,bt,c;
if(x==0){
aa=na[y][0]; ac=na[y][1]; at=na[y][2];
ba=nb[y][0]; bc=nb[y][1]; bt=nb[y][2];
da[0]=gda[y][0]; da[1]=gda[y][1]; da[2]=gda[y][2];
dc[0]=gdc[y][0]; dc[1]=gdc[y][1]; dc[2]=gdc[y][2];
dt[0]=gdt[y][0]; dt[1]=gdt[y][1]; dt[2]=gdt[y][2];
c=dif[y];
}
else{
aa=na[y][0]-na[x-1][0]; ac=na[y][1]-na[x-1][1]; at=na[y][2]-na[x-1][2];
ba=nb[y][0]-nb[x-1][0]; bc=nb[y][1]-nb[x-1][1]; bt=nb[y][2]-nb[x-1][2];
da[0]=gda[y][0]-gda[x-1][0]; da[1]=gda[y][1]-gda[x-1][1]; da[2]=gda[y][2]-gda[x-1][2];
dc[0]=gdc[y][0]-gdc[x-1][0]; dc[1]=gdc[y][1]-gdc[x-1][1]; dc[2]=gdc[y][2]-gdc[x-1][2];
dt[0]=gdt[y][0]-gdt[x-1][0]; dt[1]=gdt[y][1]-gdt[x-1][1]; dt[2]=gdt[y][2]-gdt[x-1][2];
c=dif[y]-dif[x-1];
}
if(aa!=ba || ac!=bc || at!=bt) return -1;
int res=MAX;
int rp,d=(y-x)+1;
rp=0;
for(int i=0;i<3;i++){
if(dc[i]==0) continue;
int mi;
if(i==0){
mi=min(dc[i],da[1]);
dc[i]-=mi; da[1]-=mi;
rp+=mi; c-=mi*2;
}
if(i==2){
mi=min(dc[i],dt[1]);
dc[i]-=mi; dt[1]-=mi;
rp+=mi; c-=mi*2;
}
}
for(int i=0;i<3;i++){
if(dc[i]==0) continue;
if(i==0){
rp+=dc[i]; c-=dc[i];
dt[0]+=dc[i];
dc[i]=0;
}
if(i==2){
rp+=dc[i]; c-=dc[i];
da[2]+=dc[i];
dc[i]=0;
}
}
rp+=c/2;
return rp;
}
