#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
constexpr int MAX = 1e5 + 69;
int n;
int fqa[MAX][3] = {}, fqb[MAX][3] = {};
int tf[MAX][3][3] = {};
void init(string a, string b) {
n = (int) a.size();
const auto get = [](char c) -> int
{
if (c == 'A')
return 0;
if (c == 'T')
return 1;
return 2;
};
for (int i = 1; i <= n; ++i)
{
int x = get(a[i-1]), y = get(b[i-1]);
fqa[i][x] = 1; fqb[i][y] = 1;
tf[i][x][y] = 1;
}
for (int j = 0; j < 3; ++j)
for (int i = 1; i <= n; ++i)
fqa[i][j] += fqa[i-1][j], fqb[i][j] += fqb[i-1][j];
for (int j = 0; j < 3; ++j)
for (int k = 0; k < 3; ++k)
for (int i = 1; i <= n; ++i)
tf[i][j][k] += tf[i-1][j][k];
}
int get_distance(int l, int r) {
l++, r++;
for (int i = 0; i < 3; ++i)
if (fqa[r][i] - fqa[l-1][i] != fqb[r][i] - fqb[l-1][i])
return -1;
int res = r-l+1, ctr = 0;
for (int i = 0; i < 3; ++i)
res -= (tf[r][i][i] - tf[l-1][i][i]);
for (int i = 0; i < 3; ++i)
for (int j = i+1; j < 3; ++j)
{
ctr += min(tf[r][i][j] - tf[l-1][i][j], tf[r][j][i] - tf[l-1][j][i]);
res -= 2 * min(tf[r][i][j] - tf[l-1][i][j], tf[r][j][i] - tf[l-1][j][i]);
}
assert(res % 3 == 0);
return ctr + 2*res/3;
}
