#include "dna.h"
#include <bits/stdc++.h>
#pragma GCC target("lzcnt,popcnt")
#pragma GCC optimize("O3,unroll-loops")
//#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define sp << " " <<
using namespace std;
const int inf = 2e18;
const int N = 2e5+1;
vi ca(N,0),ac(N,0),ct(N,0),tc(N,0),at(N,0),ta(N,0);
vi Aa(N,0),Ca(N,0),Ta(N,0),Ab(N,0),Cb(N,0),Tb(N,0);
int get(vi& v,int l,int r) {
return v[r]-v[l-1];
}
void init(std::string a, std::string b) {
int n = a.size();
for (int i = 1;i<=n;i++) {
Aa[i] = Aa[i-1]+(a[i-1] == 'A');
Ca[i] = Ca[i-1]+(a[i-1] == 'C');
Ta[i] = Ta[i-1]+(a[i-1] == 'T');
Ab[i] = Ab[i-1]+(b[i-1] == 'A');
Cb[i] = Cb[i-1]+(b[i-1] == 'C');
Tb[i] = Tb[i-1]+(b[i-1] == 'T');
ca[i] = ca[i-1]+(a[i-1] == 'C' && b[i-1] == 'A');
ac[i] = ac[i-1]+(a[i-1] == 'A' && b[i-1] == 'C');
ct[i] = ct[i-1]+(a[i-1] == 'C' && b[i-1] == 'T');
tc[i] = tc[i-1]+(a[i-1] == 'T' && b[i-1] == 'C');
at[i] = at[i-1]+(a[i-1] == 'A' && b[i-1] == 'T');
ta[i] = ta[i-1]+(a[i-1] == 'T' && b[i-1] == 'A');
}
}
int get_distance(int x, int y) {
x++,y++;
if (get(Aa,x,y) != get(Ab,x,y)) return -1;
if (get(Ca,x,y) != get(Cb,x,y)) return -1;
if (get(Ta,x,y) != get(Tb,x,y)) return -1;
int AC = get(ac,x,y), CA = get(ca,x,y);
int CT = get(ct,x,y), TC = get(tc,x,y);
int AT = get(at,x,y), TA = get(ta,x,y);
int ans = min(AC,CA)+min(CT,TC)+min(AT,TA);
int m1 = min(AC,CA),m2 = min(CT,TC),m3 = min(AT,TA);
AC-=m1,CA-=m1,CT-=m2,TC-=m2,AT-=m3,TA-=m3;
ans+=2*(AC+CA+CT+TC+AT+TA)/3;
return ans;
}
