#include "dna.h"
#include <bits/stdc++.h>
#include <array>
using namespace std;
inline array<int,3> combine(const array<int,3>& a, const array<int,3>& b){
return {a[0] + b[0], a[1] + b[1], a[2] + b[2]};
}
struct node{
int s,e,m;
node *l, *r;
array<int,3> v;
node(int ss,int ee):s(ss),e(ee),m((s+e)>>1),v{0,0,0}{
if(s!=e){
l=new node(s,m);
r=new node(m+1,e);
}
}
void build(int x,int y,int pos){
if(s==e){
v[0]=y;
v[1]=pos;
// v[2]=A; v[3]=C; v[4]=T;
return;
}
if(x<=m) l->build(x,y,pos);
else r->build(x,y,pos);
v=combine(l->v,r->v);
}
array<int,3> query(int x, int y){
if(x<=s && y>=e)return v;
if(y<=m) return l->query(x,y);
if(x > m) return r->query(x, y);
return combine(l->query(x,m),r->query(m+1,y));
}
};
vector<vector<int>>v;
// node *st=new node(0,1e5);
node *st=nullptr;
string aa,bb;
void init(std::string a, std::string b) {
aa=a;bb=b;
int n=a.size();
v.resize(6,vector<int>(n+1,0));
for(int i=1;i<=n;i++){
// if(i>1){
v[0][i]=v[0][i-1];v[1][i]=v[1][i-1];
v[2][i]=v[2][i-1];v[3][i]=v[3][i-1];
v[4][i]=v[4][i-1];v[5][i]=v[5][i-1];
// }
if(a[i-1]=='A')v[0][i]++; if(b[i-1]=='A')v[3][i]++;
if(a[i-1]=='C')v[1][i]++; if(b[i-1]=='C')v[4][i]++;
if(a[i-1]=='T')v[2][i]++; if(b[i-1]=='T')v[5][i]++;
}
if(st!=nullptr){
delete st;
}
st=new node(0,n-1);
for(int i=0;i<a.size();i++){
if((a[i]=='A' && b[i]=='T') || (a[i]=='T' && b[i]=='C'))st->build(i, 1, 1);
else if((a[i]=='T' && b[i]=='A') || (a[i]=='C' && b[i]=='T'))st->build(i, -1, 0);
else if(a[i]=='A' && b[i]=='C')st->build(i, 2, 1);
else if(a[i]=='C' && b[i]=='A')st->build(i,-2,0);
}
// for(int i=0;i<a.size();i++){
// if(v[i]==1)st->build(i,v[i],1,0);
// else st->build(i,v[i],0,1);
// }
}
int get_distance(int x, int y) {
if(y==x){if(aa[x]==bb[x])return 0; else return -1;}
if(y-1==x){
if(aa[x]==bb[x] && aa[y]==bb[y])return 0;
else if(aa[x]==bb[y] && bb[x]==aa[y])return 1;
else return -1;
}
if(y-2==x){
if(aa[x]==bb[x] && aa[x+1]==bb[x+1] && aa[y]==bb[y])return 0;
else if(aa[x]==bb[x] && aa[x+1]==bb[y] && aa[y]==bb[x+1])return 1;
else if(aa[x]==bb[x+1] && aa[x+1]==bb[x] && aa[y]==bb[y])return 1;
else if(aa[y]==bb[x] && aa[x+1]==bb[x+1] && aa[x]==bb[y])return 1;
else if(aa[x]==bb[y] && aa[x+1]==bb[x] && aa[x+2]==bb[x+1])return 2;
else if(aa[x]==bb[x+1] && aa[x+1]==bb[y] && aa[y]==bb[x]) return 2;
else return -1;
}
array<int, 3> result = st->query(x, y);
// for(int i:result)cout<<i<<" ";
// cout<<v[0][y+1]-v[0][x]<<" "<<v[3][y+1]-v[3][x]<<" "<<v[1][y+1]-v[1][x]<<" "<<v[4][y+1]-v[4][x]<<" "<<v[2][y+1]-v[2][x]<<" "<<v[5][y+1]-v[5][x]<<" ";
if(v[0][y+1]-v[0][x] != v[3][y+1]-v[3][x]) return -1;
if(v[1][y+1]-v[1][x] != v[4][y+1]-v[4][x]) return -1;
if(v[2][y+1]-v[2][x] != v[5][y+1]-v[5][x]) return -1;
if(result[0]!=0)return -1;
else return result[1];
}
