#include "dna.h"
#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;
vector<vector<int>> cA,cB;
vector<vector<vector<int>>> tA;
vector<int> A,B;
void init(std::string a, std::string b) {
cA.clear();
cB.clear();
tA.clear();
A.clear();
B.clear();
cA.resize(sz(a)+1,vector<int>(3,0));
cB.resize(sz(a)+1,vector<int>(3,0));
tA.resize(sz(a)+1,vector<vector<int>>(3,vector<int>(3,0)));
A.resize(sz(a)+1,0);
B.resize(sz(a)+1,0);
for (int i = 1; i <= sz(a); i++)
{
char c=a[i-1];
if(c=='A') A[i]=0;
else if(c=='T') A[i]=1;
else if(c=='C') A[i]=2;
cA[i][A[i]]++;
c=b[i-1];
if(c=='A') B[i]=0;
else if(c=='T') B[i]=1;
else if(c=='C') B[i]=2;
cB[i][B[i]]++;
if(i>0){
for (int j = 0; j < 3; j++)
{
cA[i][j]+=cA[i-1][j];
cB[i][j]+=cB[i-1][j];
}
}
tA[i][A[i]][B[i]]++;
for (int j = 0; j < 3; j++)
{
for (int k = 0; k < 3; k++)
{
tA[i][j][k]+=tA[i-1][j][k];
}
}
}
}
int get_distance(int x, int y) {
x++;
y++;
for (int j = 0; j < 3; j++)
{
if(cA[y][j]-cA[x-1][j]!=cB[y][j]-cB[x-1][j]) return -1;
}
int sm=0;
for (int j = 0; j < 3; j++)
{
for (int k = 0; k < 3; k++)
{
if(j==k) continue;
sm+=tA[y][j][k]-tA[x-1][j][k];
}
}
int rem=0;
for (int j = 0; j < 3; j++)
{
for (int k = j+1; k < 3; k++)
{
rem+=min(tA[y][j][k]-tA[x-1][j][k],tA[y][k][j]-tA[x-1][k][j]);
}
}
return max(0,(sm-rem*2)-(sm-rem*2)/3)+rem;
}
