#undef _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {cerr<<" "<<to_string(H);debug_out(T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define fi first
#define si second
typedef pair<int,int> pi;
typedef vector<int> vi;
typedef tuple<int,int,int> ti;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#include "dna.h"
const int MAXN = 100010;
int n, a[MAXN], b[MAXN];
map<char, int> idx = {{'A',0},{'T',1},{'C',2}};
int acnt[MAXN][3];
int bcnt[MAXN][3];
int pd[MAXN][3][3];
int td[MAXN][3][3][3];
int sum(int qs, int qe, int ida, int idb) {
return pd[qe][ida][idb] - pd[qs - 1][ida][idb];
}
void init(std::string A, std::string B) {
n = A.size();
for (int i = 1; i <= n; ++i) {
a[i] = idx[A[i - 1]];
b[i] = idx[B[i - 1]];
}
for (int i = 1; i <= n; ++i) {
++acnt[i][a[i]];
++bcnt[i][b[i]];
for (int j = 0; j < 3; ++j) {
acnt[i][j] += acnt[i - 1][j];
bcnt[i][j] += bcnt[i - 1][j];
}
if (a[i] != b[i])
++pd[i][a[i]][b[i]];
for (int j = 0; j < 3; ++j)
for (int k = 0; k < 3; ++k)
pd[i][j][k] += pd[i - 1][j][k];
}
}
int get_distance(int x, int y) {
++x, ++y;
for (int i = 0; i < 3; ++i)
if (acnt[y][i] - acnt[x - 1][i] != bcnt[y][i] - bcnt[x - 1][i])
return -1;
int atta = min(sum(x, y, 0, 1), sum(x, y, 1, 0));
int acca = min(sum(x, y, 0, 2), sum(x, y, 2, 0));
int tcct = min(sum(x, y, 1, 2), sum(x, y, 2, 1));
return atta + acca + tcct + abs(max(sum(x, y, 0, 1), sum(x, y, 1, 0)) - atta) * 2;
}
