#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> va, vb;
vector<int> at, ta, eq;
void init(string a, string b) {
int n = a.size();
va.assign(3, vector<int>(n + 1, 0));
vb.assign(3, vector<int>(n + 1, 0));
at.assign(n + 1, 0);
ta.assign(n + 1, 0);
eq.assign(n + 1, 0);
map<char, int> mp;
mp['A'] = 0;
mp['C'] = 1;
mp['T'] = 2;
for (int i = 0; i < n; i++) {
// copy previous
for (int j = 0; j < 3; j++) {
va[j][i + 1] = va[j][i];
vb[j][i + 1] = vb[j][i];
}
va[mp[a[i]]][i + 1]++;
vb[mp[b[i]]][i + 1]++;
at[i + 1] = at[i];
ta[i + 1] = ta[i];
eq[i + 1] = eq[i];
if (a[i] == 'A' && b[i] == 'T') at[i + 1]++;
if (a[i] == 'T' && b[i] == 'A') ta[i + 1]++;
if (a[i] == b[i]) eq[i + 1]++;
}
}
int get_distance(int x, int y) {
// IOI uses 0-based indexing
// substring is [x, y) => y is exclusive
int total = y - x;
int same = eq[y+1] - eq[x];
total -= same;
// check frequency match
for (int i = 0; i < 3; i++) {
if (va[i][y+1] - va[i][x] != vb[i][y+1] - vb[i][x]) {
return -1;
}
}
int a_t = at[y+1] - at[x];
int t_a = ta[y+1] - ta[x];
int ans = abs(a_t - t_a);
total -= 3 * ans;
ans *= 2;
ans += total / 2;
return ans;
}
