#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define all(x) x.begin(), x.end()
#define pb push_back
#define ar array
#define nl '\n'
const int N = 1e5 + 5;
int pref[N][4], A[N][3], B[N][3];
void init(std::string a, std::string b) {
int n = a.size();
for(int j = 0; j < 3; j++) {
pref[0][j] = 0;
A[0][j] = 0;
B[0][j] = 0;
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < 3; j++) {
pref[i + 1][j] = pref[i][j];
A[i + 1][j] = A[i][j];
B[i + 1][j] = B[i][j];
}
pref[i + 1][3] = pref[i][3];
pref[i + 1][0] += (a[i] != b[i]);
pref[i + 1][1] += (a[i] == 'A' && b[i] == 'T');
pref[i + 1][2] += (a[i] == 'A' && b[i] == 'C');
pref[i + 1][3] += (a[i] == 'T' && b[i] == 'A');
A[i + 1][0] += (a[i] == 'A');
A[i + 1][1] += (a[i] == 'T');
A[i + 1][2] += (a[i] == 'C');
B[i + 1][0] += (b[i] == 'A');
B[i + 1][1] += (b[i] == 'T');
B[i + 1][2] += (b[i] == 'C');
}
}
int get_distance(int x, int y) {
y++;
for(int j = 0; j < 3; j++) {
if(A[y][j] - A[x][j] != B[y][j] - B[x][j]) return -1;
}
auto get = [&](int j) {
return pref[y][j] - pref[x][j];
};
int tot_wrong = get(0), res = 0;
int temp = get(1) + get(2);
tot_wrong -= temp;
res += temp;
int x1 = get(1), x3 = get(3);
int mn = min(x1, x3);
// assert(x1 == x3);
tot_wrong -= min(x1, x3);
res += tot_wrong / 2;
return res;
}
