#include "dna.h"
#include<bits/stdc++.h>
using namespace std;
int n;
string s, t;
vector<map<char, int>> prefs, preft;
vector<vector<int>> cnt;
int get (int l, int r, vector<map<char, int>> &pref, char c) {
return pref[r][c] - (l ? pref[l - 1][c] : 0);
}
void init(std::string a, std::string b) {
s = a; t = b;
n = a.size();
prefs.resize(n);
preft.resize(n);
cnt.resize(n, vector<int>(6));
for (int i = 0; i < n; i++) {
prefs[i][s[i]]++;
preft[i][t[i]]++;
if (s[i] == 'A') {
if (t[i] == 'T') cnt[i][0]++;
if (t[i] == 'C') cnt[i][2]++;
}
if (s[i] == 'T') {
if (t[i] == 'A') cnt[i][1]++;
if (t[i] == 'C') cnt[i][4]++;
}
if (s[i] == 'C') {
if (t[i] == 'A') cnt[i][3]++;
if (t[i] == 'T') cnt[i][5]++;
}
}
for (int i = 1; i < n; i++) {
for (auto e: {'A', 'T', 'C'}) {
prefs[i][e] += prefs[i - 1][e];
preft[i][e] += preft[i - 1][e];
}
for (int j = 0; j < 6; j++) cnt[i][j] += cnt[i - 1][j];
}
}
int get_distance(int x, int y) {
for (auto e: {'A', 'T', 'C'}) {
if (get(x, y, prefs, e) != get(x, y, preft, e)) return -1;
}
int ans = 0;
vector<int> cur(6);
for (int i = 0; i < 6; i++) {
cur[i] = cnt[y][i] - (x ? cnt[x - 1][i] : 0);
}
for (int i = 0; i < 6; i += 2) {
int c = min(cur[i], cur[i + 1]);
ans += c;
cur[i] -= c;
cur[i + 1] -= c;
}
int k = cur[0] + cur[1];
ans += (k ? k - 1 : 0);
return ans;
}
