#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n;
string a, b;
struct Node{
int ac, ca, at, ta, ct, tc;
Node(){
ac = ca = at = ta = ct = tc = 0;
}
void add(char x, char y){
if(x == 'A' && y == 'C') ac++;
if(x == 'C' && y == 'A') ca++;
if(x == 'A' && y == 'T') at++;
if(x == 'T' && y == 'A') ta++;
if(x == 'C' && y == 'T') ct++;
if(x == 'T' && y == 'C') tc++;
}
Node operator + (const Node &sc) const{
Node c;
c.ac = ac + sc.ac;
c.ca = ca + sc.ca;
c.at = at + sc.at;
c.ta = ta + sc.ta;
c.ct = ct + sc.ct;
c.tc = tc + sc.tc;
return c;
}
};
struct SegTree{
Node tree[N * 4];
void build(int v = 1, int l = 0, int r = n - 1){
if(l == r) tree[v].add(a[l], b[l]);
else{
int m = l + (r - l) / 2;
build(v * 2, l, m);
build(v * 2 + 1, m + 1, r);
tree[v] = tree[v * 2] + tree[v * 2 + 1];
}
}
Node query(int l, int r, int v = 1, int tl = 0, int tr = n - 1){
if(l > r) return Node();
else if(tl == l && tr == r) return tree[v];
else{
int tm = tl + (tr - tl) / 2;
return query(l, min(tm, r), v * 2, tl, tm) + query(max(l, tm + 1), r, v * 2 + 1, tm + 1, tr);
}
}
};
SegTree sgt;
void init(string inp_a, string inp_b){
a = inp_a, b = inp_b;
n = a.size();
sgt.build();
}
int get_distance(int x, int y){
Node v = sgt.query(x, y);
int ans = 0, tmp;
tmp = min(v.ac, v.ca);
ans += tmp;
v.ac -= tmp;
v.ca -= tmp;
tmp = min(v.at, v.ta);
ans += tmp;
v.at -= tmp;
v.ta -= tmp;
tmp = min(v.ct, v.tc);
ans += tmp;
v.ct -= tmp;
v.tc -= tmp;
if(v.ac == v.ct && v.ct == v.ta) ans += v.ac * 2;
else return -1;
if(v.ca == v.at && v.at == v.tc) ans += v.ca * 2;
else return -1;
return ans;
}
