#include "dna.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
vector<int> A, T, C, AT, CT, AC, TC, CA, TA;
void init(str a, str b){
int n = a.size();
A.assign(n, 0);
T.assign(n, 0);
C.assign(n, 0);
AT.assign(n, 0);
CT.assign(n, 0);
AC.assign(n, 0);
TC.assign(n, 0);
CA.assign(n, 0);
TA.assign(n, 0);
for(int i = 0; i < n; i++){
if(i != 0) A[i] = A[i-1], T[i] = T[i-1], C[i] = C[i-1];
if(a[i] == 'A') A[i]++;
if(a[i] == 'T') T[i]++;
if(a[i] == 'C') C[i]++;
if(b[i] == 'A') A[i]--;
if(b[i] == 'T') T[i]--;
if(b[i] == 'C') C[i]--;
}
for(int i = 0; i < n; i++){
if(i != 0)
AT[i] = AT[i-1], CT[i] = CT[i-1],
AC[i] = AC[i-1], TC[i] = TC[i-1],
CA[i] = CA[i-1], TA[i] = TA[i-1];
if(a[i] == 'A' && b[i] == 'T') AT[i]++;
if(a[i] == 'C' && b[i] == 'T') CT[i]++;
if(a[i] == 'A' && b[i] == 'C') AC[i]++;
if(a[i] == 'T' && b[i] == 'C') TC[i]++;
if(a[i] == 'C' && b[i] == 'A') CA[i]++;
if(a[i] == 'T' && b[i] == 'A') TA[i]++;
}
}
int getsum(int l, int r, vector<int> &v){
return v[r]-(l == 0 ? 0: v[l-1]);
}
int getmn(int &a, int &b){
int mn = min(a, b);
a-=mn, b-=mn;
return mn;
}
int get_distance(int l, int r){
if(getsum(l, r, A) != 0 || getsum(l, r, C) != 0 || getsum(l, r, T) != 0) return -1;
int at = getsum(l, r, AT), ct = getsum(l, r, CT);
int ac = getsum(l, r, AC), tc = getsum(l, r, TC);
int ca = getsum(l, r, CA), ta = getsum(l, r, TA);
int ans = 0;
ans+=getmn(at, ta);
ans+=getmn(ct, tc);
ans+=getmn(ac, ca);
if(at != 0) ans+=at+tc+ca-min(at, min(tc, ca));
else ans+=ta+ac+ct-min(ta, min(ac, ct));
return ans;
}
