#include "dna.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n;
string A, B;
char C[3] = {'A', 'T', 'C'};
map <pair <char, char>, vector <int>> P;
void init(string a, string b) {
A = " " + a, B = " " + b;
n = a.size();
for (auto &x : C) for (auto &y : C) P[{x, y}].resize(n+1);
for (int i = 1; i <= n; i++) {
for (auto &x : C) for (auto &y : C) P[{x, y}][i] = P[{x, y}][i-1];
if (A[i] != B[i]) P[{A[i], B[i]}][i]++;
}
}
int get_distance(int l, int r) {
r++;
map <char, int> ca, cb;
map <pair <char, char>, int> cnt;
for (auto &x : C) for (auto &y : C) {
ca[x] += P[{x, y}][r] - P[{x, y}][l];
cb[y] += P[{x, y}][r] - P[{x, y}][l];
cnt[{x, y}] = P[{x, y}][r] - P[{x, y}][l];
}
// for (auto &e : C) cout << e << ' ' << ca[e] << ' ' << cb[e] << '\n';
for (auto &e : C) if (ca[e] != cb[e]) return -1;
return cnt[{'A', 'T'}] + cnt[{'A', 'C'}] + (ca['C'] + ca['T'] - min(cnt[{'A', 'T'}], cnt[{'T', 'A'}]) + min(cnt[{'A', 'C'}], cnt[{'C', 'A'}])) / 2;
}
