#include <bits/stdc++.h>
//#include "grader.cpp"
#include "dna.h"
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define el "\n"
using namespace std;
const int N = 2e5 + 500;
vector <int> in_a[26], in_b[26];
int pf[3][3][N];
int n;
vector <char> sb;
void init(string a, string b) {
n = sz(a);
map <char, int> mp;
mp['A'] = 0;
mp['C'] = 1;
mp['T'] = 2;
for (int i = 0; i < sz(a); i++) {
in_a[a[i] - 'A'].pb(i);
in_b[b[i] - 'A'].pb(i);
pf[mp[a[i]]][mp[b[i]]][i]++;
}
for (int a = 0; a < 3; a++) {
for (int b = 0; b < 3; b++) {
for (int i = 1; i < n; i++) {
pf[a][b][i] += pf[a][b][i - 1];
}
}
}
sb = {'A', 'C', 'T'};
}
int get_distance(int x, int y) {
for (auto c : sb) {
int L = lower_bound(all(in_a[c - 'A']), x) - in_a[c - 'A'].begin();
int R = upper_bound(all(in_a[c - 'A']), y) - in_a[c - 'A'].begin();
int l = lower_bound(all(in_b[c - 'A']), x) - in_b[c - 'A'].begin();
int r = upper_bound(all(in_b[c - 'A']), y) - in_b[c - 'A'].begin();
if (R - L != r - l) {
return -1;
}
}
vector <vector <int> > cnt(3, vector <int> (3, 0));
for (int a = 0; a < 3; a++) {
for (int b = 0; b < 3; b++) {
cnt[a][b] = pf[a][b][y] - (x ? pf[a][b][x - 1] : 0);
}
}
int ans = 0;
for (int a = 0; a < 3; a++) {
for (int b = 0; b < 3; b++) {
if (a == b) {
continue;
}
int cur = min(cnt[a][b], cnt[b][a]);
ans += cur;
cnt[a][a] += cur; cnt[a][b] -= cur;
cnt[b][b] += cur; cnt[b][a] -= cur;
}
}
int add = 0;
for (int a = 0; a < 3; a++) {
for (int b = 0; b < 3; b++) {
if (a == b) {
continue;
}
add += cnt[a][b];
}
}
assert(add % 3 == 0);
return ans + add - add / 3;
}
