#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
inline namespace tc
{
} // namespace tc
namespace
{
array<vector<int>, 3> pref_a, pref_b;
vector<int> diff;
array<array<vector<int>, 3>, 3> cnt;
} // namespace
const map<char, int> mp = {{pair('A', 0), pair('T', 1), pair('C', 2)}};
void init(string a, string b)
{
int n = (int)a.length();
pref_a.fill(vector<int>(n + 1, 0)), pref_b.fill(vector<int>(n + 1, 0));
diff = vector<int>(n + 1, 0);
for (int c = 0; c < 3; c++)
cnt[c].fill(vector<int>(n + 1, 0));
for (int i = 0; i < n; i++)
{
for (int c = 0; c < 3; c++)
{
pref_a[c][i + 1] = pref_a[c][i], pref_b[c][i + 1] = pref_b[c][i];
for (int d = 0; d < 3; d++)
cnt[c][d][i + 1] = cnt[c][d][i];
}
pref_a[mp.at(a[i])][i + 1]++, pref_b[mp.at(b[i])][i + 1]++;
diff[i + 1] = diff[i] + (a[i] != b[i]);
cnt[mp.at(a[i])][mp.at(b[i])][i + 1]++;
}
}
int get_distance(int x, int y)
{
++y;
bool ok = 1;
for (int c = 0; c < 3; c++)
ok &= pref_a[c][y] - pref_a[c][x] == pref_b[c][y] - pref_b[c][x];
if (ok)
{
int res = 0;
int rem = diff[y] - diff[x];
for (int c = 0; c < 3; c++)
{
for (int d = c + 1; d < 3; d++)
{
int k = min(cnt[c][d][y] - cnt[c][d][x], cnt[d][c][y] - cnt[d][c][x]);
res += k;
rem -= 2 * k;
}
}
assert(rem % 3 == 0);
res += rem / 3 * 2;
return res;
}
return -1;
}
