#include "dna.h"
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
ll n = 100000;
vector<ll> ac(n), ca(n), at(n), ta(n), ct(n), tc(n);
void init(string a, string b) {
for (int i = 0; i < min((ll)a.size(), n); i++) {
if (i == 0) {
ac[i] = (a[i] == 'A' and b[i] == 'C');
ca[i] = (a[i] == 'C' and b[i] == 'A');
ct[i] = (a[i] == 'C' and b[i] == 'T');
tc[i] = (a[i] == 'T' and b[i] == 'C');
at[i] = (a[i] == 'A' and b[i] == 'T');
ta[i] = (a[i] == 'T' and b[i] == 'A');
} else {
ac[i] = ac[i - 1] + (a[i] == 'A' and b[i] == 'C');
ca[i] = ca[i - 1] + (a[i] == 'C' and b[i] == 'A');
ct[i] = ct[i - 1] + (a[i] == 'C' and b[i] == 'T');
tc[i] = tc[i - 1] + (a[i] == 'T' and b[i] == 'C');
at[i] = at[i - 1] + (a[i] == 'A' and b[i] == 'T');
ta[i] = ta[i - 1] + (a[i] == 'T' and b[i] == 'A');
}
}
}
int get_distance(int x, int y) {
if (x == 0) {
if (ac[y] + at[y] != ca[y] + ta[y])
return -1;
if (tc[y] + ta[y] != ct[y] + at[y])
return -1;
if (ct[y] + ca[y] != tc[y] + ac[y])
return -1;
ll find = min(ac[y], ca[y]) + min(tc[y], ct[y]) + min(at[y], ta[y]);
ll mis = ac[y] + ca[y] + tc[y] + ct[y] + at[y] + ta[y];
ll rem = mis - 2 * find;
return find + 2 * rem / 3;
} else {
if (ac[y] - ac[x - 1] + at[y] - at[x - 1] != ca[y] - ca[x - 1] + ta[y] - ta[x - 1])
return -1;
if (tc[y] - tc[x - 1] + ta[y] - ta[x - 1] != ct[y] - ct[x - 1] + at[y] - at[x - 1])
return -1;
if (ct[y] - ct[x - 1] + ca[y] - ca[x - 1] != tc[y] - tc[x - 1] + ac[y] - ac[x - 1])
return -1;
ll find = min(ac[y] - ac[x - 1], ca[y] - ca[x - 1]) + min(tc[y] - tc[x - 1], ct[y] - ct[x - 1]) + min(at[y] - at[x - 1], ta[y] - ta[x - 1]);
ll mis = ac[y] + ca[y] + tc[y] + ct[y] + at[y] + ta[y] - ac[x - 1] - ca[x - 1] - tc[x - 1] - ct[x - 1] - at[x - 1] - ta[x - 1];
ll rem = mis - 2 * find;
return find + 2 * rem / 3;
}
}
