#include "dna.h"
#include <bits/stdc++.h>
namespace {
const int N = 1e5 + 5;
int n;
int A[3][N], B[3][N], pf[6][N];
std::vector<char> c = {'A', 'T', 'C'};
std::vector<std::array<char, 2>> pat = {{'A', 'T'}, {'T', 'A'}, {'A', 'C'}, {'C', 'A'}, {'T', 'C'}, {'C', 'T'}};
int qry(int l, int r, int *pf) {
return pf[r] - (l ? pf[l - 1] : 0);
}
}
void init(std::string a, std::string b) {
n = a.size();
for (int i = 0; i < n; ++i) {
for (int j = 0; j < 3; ++j) {
A[j][i] = i ? A[j][i - 1] : 0;
B[j][i] = i ? B[j][i - 1] : 0;
}
for (int j = 0; j < 6; ++j) {
pf[j][i] = i ? pf[j][i - 1] : 0;
}
++A[find(c.begin(), c.end(), a[i]) - c.begin()][i];
++B[find(c.begin(), c.end(), b[i]) - c.begin()][i];
if (a[i] != b[i]) {
++pf[find(pat.begin(), pat.end(), std::array<char, 2>{a[i], b[i]}) - pat.begin()][i];
}
}
}
int get_distance(int x, int y) {
for (int j = 0; j < 3; ++j) {
if (qry(x, y, A[j]) != qry(x, y, B[j])) {
return -1;
}
}
std::array<int, 6> cnt{};
for (int i = 0; i < 6; ++i) {
cnt[i] = qry(x, y, pf[i]);
}
int res = 0, tot = 0;
for (int i = 0; i < 6; i += 2) {
int k = std::min(cnt[i], cnt[i + 1]);
cnt[i] -= k;
cnt[i + 1] -= k;
res += k;
tot += cnt[i] + cnt[i + 1];
}
return res + 2 * tot / 3;
}
