#include <bits/stdc++.h>
// mrrrow meeow :3
// go play vivid/stasis now! it's free on steam
#define fo(i, a, b) for (auto i = (a); i < (b); i++)
#define of(i, a, b) for (auto i = (b); i-- > (a);)
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
#define be(a) a.begin(), a.end()
using namespace std;
int ____init = [] {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
return 0;
}();
struct Node {
int ne = 0;
int aa = 0, at = 0, ac = 0;
int ba = 0, bt = 0, bc = 0;
Node operator+(const Node &other) const {
Node res;
res.ne = ne + other.ne;
res.aa = aa + other.aa;
res.at = at + other.at;
res.ac = ac + other.ac;
res.ba = ba + other.ba;
res.bt = bt + other.bt;
res.bc = bc + other.bc;
return res;
}
Node operator-(const Node &other) const {
Node res;
res.ne = ne - other.ne;
res.aa = aa - other.aa;
res.at = at - other.at;
res.ac = ac - other.ac;
res.ba = ba - other.ba;
res.bt = bt - other.bt;
res.bc = bc - other.bc;
return res;
}
bool valid() const {
return aa == ba && at == bt && ac == bc;
}
};
Node bit[100001];
Node get(int i) {
Node res;
for (i++; i > 0; i -= i & -i) res = res + bit[i];
return res;
}
void add(int i, Node v) {
for (i++; i <= 100000; i += i & -i) bit[i] = bit[i] + v;
}
string _a, _b;
void init(string a, string b) {
_a = a, _b = b;
fo(i, 0, a.size()) {
Node res;
res.ne = a[i] != b[i];
res.aa = a[i] == 'A';
res.at = a[i] == 'T';
res.ac = a[i] == 'C';
res.ba = b[i] == 'A';
res.bt = b[i] == 'T';
res.bc = b[i] == 'C';
add(i, res);
}
}
int get_distance(int x, int y) {
string a(_a), b(_b);
int swaps = 0;
fo(i, x, y + 1) {
if (a[i] == b[i]) continue;
fo(j, i + 1, y + 1) {
if (a[j] == b[i]) {
swap(a[i], a[j]);
swaps++;
goto cont;
}
}
return -1;
cont:;
}
return swaps;
Node res = get(y) - get(x - 1);
return res.valid() ? max(res.ne - 1, 0) : -1;
}
