#include<bits/stdc++.h>
using namespace std;
struct Node {
int changes = 0;
int at = 0, tc = 0, ca = 0;
} ;
typedef pair<int, int> pii;
constexpr int siz = (1 << 17); // 1 << 17
Node segment_tree[siz * 2 + 1];
void update(int pos, char a, char b)
{
Node change = { (a != b),
(a == 'A' && b == 'T') - (b == 'A' && a == 'T'),
(a == 'T' && b == 'C') - (b == 'T' && a == 'C'),
(a == 'C' && b == 'A') - (b == 'C' && a == 'A')};
if (change.changes == 0) return ;
while (pos > 0) {
segment_tree[pos].at += change.at;
segment_tree[pos].tc += change.tc;
segment_tree[pos].ca += change.ca;
segment_tree[pos].changes += change.changes;
pos /= 2;
}
}
Node rangeq(int pos, pii wan, pii sear)
{
// Out of interval
if (wan.second < sear.first || sear.second < wan.first)
return Node{0,0,0,0};
// All in interval
if (wan.first <= sear.first && sear.second <= wan.second)
return segment_tree[pos];
int mid = (sear.first + sear.second) / 2;
Node left = rangeq(pos * 2, wan, pii(sear.first, mid)),
right = rangeq(pos * 2 + 1, wan, pii(mid + 1, sear.second));
left.at += right.at;
left.tc += right.tc;
left.ca += right.ca;
left.changes += right.changes;
return left;
}
int query(int x, int y)
{
Node r = rangeq(1, pii(x, y), pii(0, siz - 1));
if ((r.at != r.tc) || (r.ca != r.tc)) return -2;
return r.changes + abs(r.at);
}
void init(string a, string b)
{
for (int i = 0; i < a.size(); i++) {
update(i + siz, a[i], b[i]);
}
}
int get_distance(int x, int y)
{
return query(x, y) / 2;
}
