#include "dna.h"
#include <bits/stdc++.h>
#define N 100005
using namespace std;
struct node{
int a1,t1,c1;
int a2,t2,c2;
int at,ac;
int ta,tc;
int ca,ct;
node(){
a1 = t1 = c1 = a2 = t2 = c2 = 0;
at = ac = ta = tc = ca = ct = 0;
}
};
node pre[N];
node add(node a,node b,int coef){
a.a1 += b.a1 * coef;
a.t1 += b.t1 * coef;
a.c1 += b.c1 * coef;
a.a2 += b.a2 * coef;
a.t2 += b.t2 * coef;
a.c2 += b.c2 * coef;
a.at += b.at * coef;
a.ac += b.ac * coef;
a.ta += b.ta * coef;
a.tc += b.tc * coef;
a.ca += b.ca * coef;
a.ct += b.ct * coef;
return a;
}
void init(string a, string b) {
int n = a.size();
for(int i = 0;i<n;i++){
if(a[i] == 'A'){
pre[i].a1++;
}
if(a[i] == 'T'){
pre[i].t1++;
}
if(a[i] == 'C'){
pre[i].c1++;
}
if(b[i] == 'A'){
pre[i].a2++;
}
if(b[i] == 'T'){
pre[i].t2++;
}
if(b[i] == 'C'){
pre[i].c2++;
}
if(a[i] == 'A' && b[i] == 'T'){
pre[i].at++;
}
if(a[i] == 'A' && b[i] == 'C'){
pre[i].ac++;
}
if(a[i] == 'T' && b[i] == 'A'){
pre[i].ta++;
}
if(a[i] == 'T' && b[i] == 'C'){
pre[i].tc++;
}
if(a[i] == 'C' && b[i] == 'A'){
pre[i].ca++;
}
if(a[i] == 'C' && b[i] == 'T'){
pre[i].ct++;
}
if(i){
pre[i] = add(pre[i],pre[i-1],1);
}
}
}
int get_distance(int x, int y) {
node val = pre[y];
if(x){
val = add(val,pre[x-1],-1);
}
if(val.a1 != val.a2 || val.t1 != val.t2 || val.c1 != val.c2){
return -1;
}
int ans = 0;
int mini = -1;
mini = min(val.at,val.ta);
ans += mini;
val.at -= mini;
val.ta -= mini;
mini = min(val.ac,val.ca);
ans += mini;
val.ac -= mini;
val.ca -= mini;
mini = min(val.tc,val.ct);
ans += mini;
val.tc -= mini;
val.ct -= mini;
ans += max(val.at,val.ac)*2;
return ans;
}
