#include<bits/stdc++.h>
#include "dna.h"
using namespace std;
vector<int> match, ac, ca, at, ta, ct, tc, A, C, T;
void init(std::string a, std::string b) {
int n = a.size();
match.resize(n,0);
ac.resize(n,0);
ca.resize(n,0);
at.resize(n,0);
ta.resize(n,0);
ct.resize(n,0);
tc.resize(n,0);
A.resize(n,0);
C.resize(n,0);
T.resize(n,0);
for(int i = 0; i < n; ++i){
if(a[i] == b[i])match[i]=1;
if(a[i] == 'A' && b[i] == 'C')ac[i]=1;
if(a[i] == 'C' && b[i] == 'A')ca[i]=1;
if(a[i] == 'A' && b[i] == 'T')at[i]=1;
if(a[i] == 'T' && b[i] == 'A')ta[i]=1;
if(a[i] == 'C' && b[i] == 'T')ct[i]=1;
if(a[i] == 'T' && b[i] == 'C')tc[i]=1;
if(a[i] == 'A')A[i]++;
if(a[i] == 'C')C[i]++;
if(a[i] == 'T')T[i]++;
if(b[i] == 'A')A[i]--;
if(b[i] == 'C')C[i]--;
if(b[i] == 'T')T[i]--;
}
for(int i = 1; i < n; ++i){
match[i]+=match[i-1];
ac[i]+=ac[i-1];
ca[i]+=ca[i-1];
at[i]+=at[i-1];
ta[i]+=ta[i-1];
ct[i]+=ct[i-1];
tc[i]+=tc[i-1];
A[i]+=A[i-1];
C[i]+=C[i-1];
T[i]+=T[i-1];
}
}
int get_distance(int x, int y) {
int ans = 0;
int dis = y-x+1;
if(x == 0){
if(A[y]|C[y]|T[y])return -1;
dis-=match[y];
ans+=min(ac[y],ca[y]);
ans+=min(at[y],ta[y]);
ans+=min(tc[y],ct[y]);
dis-=2*ans;
return ans+(dis/3)*2;
}
else{
if((A[y]-A[x-1])|(C[y]-C[x-1])|(T[y]-T[x-1]))return -1;
dis-=match[y]-match[x-1];
ans+=min(ac[y]-ac[x-1],ca[y]-ca[x-1]);
ans+=min(at[y]-at[x-1],ta[y]-ta[x-1]);
ans+=min(tc[y]-tc[x-1],ct[y]-ct[x-1]);
dis-=2*ans;
return ans+(dis/3)*2;
}
}
