#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][5], 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][4] = pref[i][4];
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');
pref[i + 1][4] += (a[i] == 'C' && 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;
tot_wrong -= get(1) + get(2);
res += get(1) + get(2);
// res += tot_wrong / 2;
// int x1 = get(1), x3 = get(3);
// int mn = min(x1, x3);
// assert(x1 == x3);
// x3 -= mn;
// tot_wrong -= min(x1, x3);
// res += tot_wrong / 2;
// cout << "wrong: " << tot_wrong << nl;
tot_wrong -= min( get(1), get(3) );
tot_wrong -= min( get(2), get(4) );
// cout << min(get(1), get(3)) << ' ' << min(get(2), get(4)) << nl;
// cout << "wrong: " << tot_wrong << nl;
assert(tot_wrong % 2 == 0);
res += tot_wrong / 2;
return res;
}
