#include "dna.h"
#include <bits/stdc++.h>
#define vi vector<int>
using namespace std;
vi at;
vi ta;
vi ac;
vi ca;
vi tc;
vi ct;
vi A;
vi T;
vi C;
void init(std::string a, std::string b) {
int n=a.size();
at.resize(n);
ac.resize(n);
ct.resize(n);
tc.resize(n);
ta.resize(n);
ca.resize(n);
C.resize(n);
A.resize(n);
T.resize(n);
for(int i=0;i<n;i++){
if(i){
ta[i]+=ta[i-1];ca[i]+=ca[i-1];tc[i]+=tc[i-1];ac[i]+=ac[i-1];at[i]+=at[i-1];ct[i]+=ct[i-1];
A[i]+=A[i-1];
C[i]+=C[i-1];
T[i]+=T[i-1];
}
if(a[i]=='T'){
T[i]++;
if(b[i]=='A')ta[i]++;
if(b[i]=='C')tc[i]++;
}
if(a[i]=='A'){
A[i]++;
if(b[i]=='T')at[i]++;
if(b[i]=='C')ac[i]++;
}
if(a[i]=='C'){
C[i]++;
if(b[i]=='A')ca[i]++;
if(b[i]=='T')ct[i]++;
}
if(b[i]=='A')A[i]--;
if(b[i]=='T')T[i]--;
if(b[i]=='C')C[i]--;
}
}
int get_distance(int x, int y) {
int cost=0;
int dac=0,dat=0,dta=0,dtc=0,dca=0,dct=0;
int a=0,t=0,c=0;
if(x){
dac-=ac[x-1];
dat-=at[x-1];
dtc-=tc[x-1];
dta-=ta[x-1];
dca-=ca[x-1];
dct-=ct[x-1];
a-=A[x-1];
t-=T[x-1];
c-=C[x-1];
}
a+=A[y];
t+=T[y];
c+=C[y];
if(a || t || c)return -1;
dac+=ac[y];
dat+=at[y];
dtc+=tc[y];
dta+=ta[y];
dca+=ca[y];
dct+=ct[y];
if(dac<dca)swap(dac,dca);
if(dat<dta)swap(dat,dta);
if(dct<dtc)swap(dtc,dct);
cost=dca+dta+dtc;
int left=dac+dat+dct-cost;
cost+=2*left/3;
return cost;
}
