#include <bits/stdc++.h>
using namespace std;
#include "dna.h"
const int nax=1e5+5;
struct DNA{
int sumA,sumT,sumC,at,ac,ct,ca,ta,tc;
DNA() : sumA(0),sumT(0),sumC(0),at(0),ac(0),ct(0),ca(0),ta(0),tc(0) {}
};
DNA segtree[nax*4];
string s,t;
DNA merge(DNA a,DNA b){
DNA ans;
ans.sumA=a.sumA+b.sumA;
ans.sumT=a.sumT+b.sumT;
ans.sumC=a.sumC+b.sumC;
ans.ac=a.ac+b.ac;
ans.tc=a.tc+b.tc;
ans.ca=a.ca+b.ca;
ans.ct=a.ct+b.ct;
ans.ta=a.ta+b.ta;
ans.at=a.at+b.at;
return ans;
}
void build(int pos,int l,int r){
if(l==r){
if(s[l]=='A'){
segtree[pos].sumA++;
if(t[l]=='C') segtree[pos].ac++;
if(t[l]=='T') segtree[pos].at++;
}
if(s[l]=='T'){
segtree[pos].sumT++;
if(t[l]=='C') segtree[pos].tc++;
if(t[l]=='A') segtree[pos].ta++;
}
if(s[l]=='C'){
segtree[pos].sumC++;
if(t[l]=='A') segtree[pos].ca++;
if(t[l]=='T') segtree[pos].ct++;
}
return;
}
int mid=(r+l)/2;
build(pos*2+1,l,mid);
build(pos*2+2,mid+1,r);
segtree[pos]=merge(segtree[pos*2+1],segtree[pos*2+2]);
}
DNA nabba;
DNA query(int pos,int l,int r,int left,int right){
if(l>r||l>right||r<left) return nabba;
if(l>=left&&r<=right) return segtree[pos];
int mid=(r+l)/2;
return merge(query(pos*2+1,l,mid,left,right),query(pos*2+2,mid+1,r,left,right));
}
int pre[nax][3];
int n;
void init(std::string a, std::string b) {
s=a;
t=b;
n=t.size();
build(0,0,n-1);
for (int i = 0; i < n; ++i)
{
pre[i+1][0]=pre[i][0]+(t[i]=='A');
pre[i+1][1]=pre[i][1]+(t[i]=='T');
pre[i+1][2]=pre[i][2]+(t[i]=='C');
}
return;
}
int get_distance(int x, int y){
int a=pre[y+1][0]-pre[x][0];
int t=pre[y+1][1]-pre[x][1];
int c=pre[y+1][2]-pre[x][2];
DNA ans=query(0,0,n-1,x,y);
if(ans.sumA!=a||ans.sumT!=t||ans.sumC!=c) return -1;
return max(ans.ta,ans.at)+max(ans.ca,ans.ac);
}
