#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll cnt[100005][3][3], N;
ll freqA[100005][3], freqB[100005][3];
void init(string A, string B) {
N = A.size();
auto conv = [&](char C) {
if (C == 'A') return 0;
if (C == 'T') return 1;
return 2;
};
for (int i = 0; i < N; i++) {
for (int j = 0; j < 3; j++) {
for (int k = 0; k < 3; k++) {
if (i) cnt[i][j][k] = cnt[i-1][j][k];
}
if (i) {
freqA[i][j] = freqA[i-1][j];
freqB[i][j] = freqB[i-1][j];
}
}
freqA[i][conv(A[i])]++;
freqB[i][conv(B[i])]++;
cnt[i][conv(A[i])][conv(B[i])]++;
}
}
int get_distance(int x, int y) {
// check if freq the same
for (int i = 0; i < 3; i++) {
if (freqA[y][i]-(!x ? 0LL : freqA[x-1][i]) != freqB[y][i]-(!x ? 0LL : freqB[x-1][i])) return -1;
}
auto get = [&](ll a, ll b, ll i, ll j) {
if (!i) return cnt[j][a][b];
return cnt[j][a][b]-cnt[i-1][a][b];
};
ll cur = y-x+1, ans = 0;
for (int i = 0; i < 3; i++) {
cur -= get(i, i, x, y);
for (int j = i+1; j < 3; j++) {
cur -= min(get(i, j, x, y), get(j, i, x, y))*2LL;
ans += min(get(i, j, x, y), get(j, i, x, y));
}
}
assert(cur%3 == 0);
return ans+(cur*2)/3;
}
