#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 nat = 0, nac = 0;
int nta = 0, ntc = 0;
int nca = 0, nct = 0;
int aa = 0, at = 0, ac = 0;
int ba = 0, bt = 0, bc = 0;
Node operator+(const Node &other) const {
Node res;
res.nat = nat + other.nat;
res.nac = nac + other.nac;
res.nta = nta + other.nta;
res.ntc = ntc + other.ntc;
res.nca = nca + other.nca;
res.nct = nct + other.nct;
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.nat = nat - other.nat;
res.nac = nac - other.nac;
res.nta = nta - other.nta;
res.ntc = ntc - other.ntc;
res.nca = nca - other.nca;
res.nct = nct - other.nct;
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;
}
int swaps() const {
if (!valid()) return -1;
Node res = *this;
int sac = min(res.nac, res.nca);
int stc = min(res.ntc, res.nct);
return res.nca + res.nct + min(res.nta + res.nca - sac, res.nat + res.nct - stc);
}
};
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;
}
void init(string a, string b) {
fo(i, 0, a.size()) {
Node res;
res.nat = a[i] == 'A' && b[i] == 'T';
res.nac = a[i] == 'A' && b[i] == 'C';
res.nta = a[i] == 'T' && b[i] == 'A';
res.ntc = a[i] == 'T' && b[i] == 'C';
res.nca = a[i] == 'C' && b[i] == 'A';
res.nct = a[i] == 'C' && b[i] == 'T';
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) {
return (get(y) - get(x - 1)).swaps();
}
