#include "dna.h"
#include <iostream>
#include<map>
//#include<pair>
using namespace std; int ct[1000100],tc[1000100],att[1000100],ta[1001000],ca[1000100],ac[1001000];
int AA[1000100],CC[1000100],TT[1001000]; int AA2[1000100],CC2[1000100],TT2[1001000];
string s="",c="";
map<pair<char,char>,int>m;
void init(string a, string b) {
s=a;
c=b; int n=s.size();
ct[0]=(s[0]=='C'&&c[0]=='T');
tc[0]=(s[0]=='T'&&c[0]=='C');
att[0]=(s[0]=='A'&&c[0]=='T');
ta[0]=(s[0]=='T'&&c[0]=='A');
ac[0]=(s[0]=='A'&&c[0]=='C');
ca[0]=(s[0]=='C'&&c[0]=='A');
for(int i=1;i<n;i++)
{
ct[i]=ct[i-1]+(s[i]=='C'&&c[i]=='T');
tc[i]=(s[i]=='T'&&c[i]=='C')+tc[i-1];
att[i]=(s[i]=='A'&&c[i]=='T')+att[i-1];
ta[i]=(s[i]=='T'&&c[i]=='A')+ta[i-1];
ac[i]=(s[i]=='A'&&c[i]=='C')+ac[i-1];
ca[i]=(s[i]=='C'&&c[i]=='A')+ca[i-1];
}
int aa=0,cc=0,tt=0;
for(int i=0;i<n;i++)
{
if(s[i]=='A')
aa++;
if(s[i]=='T')
tt++;
if(s[i]=='C')
cc++;
AA[i]=aa;
CC[i]=cc;
TT[i]=tt;
}
int aa2=0,cc2=0,tt2=0;
for(int i=0;i<n;i++)
{
if(c[i]=='A')
aa2++;
if(c[i]=='T')
tt2++;
if(c[i]=='C')
cc2++;
AA2[i]=aa2;
CC2[i]=cc2;
TT2[i]=tt2;
}
}
int get_distance(int x, int y) {
m[{'C','T'}]=0;
m[{'T','C'}]=0;
m[{'A','T'}]=0;
m[{'T','A'}]=0;
m[{'C','A'}]=0;
m[{'A','C'}]=0;
int A=0,C=0,T=0,A2=0,C2=0,T2=0;
if(x>0)
{
A=AA[y]-AA[x-1];
C=CC[y]-CC[x-1];
T=TT[y]-TT[x-1];
A2=AA2[y]-AA2[x-1];
C2=CC2[y]-CC2[x-1];
T2=TT2[y]-TT2[x-1];
m[{'C','T'}]=ct[y]-ct[x-1];
m[{'T','C'}]=tc[y]-tc[x-1];
m[{'A','T'}]=att[y]-att[x-1];
m[{'T','A'}]=ta[y]-ta[x-1];
m[{'C','A'}]=ca[y]-ca[x-1];
m[{'A','C'}]=ac[y]-ac[x-1];
}
else
{
A=AA[y];
C=CC[y];
T=TT[y];
A2=AA2[y];
C2=CC2[y];
T2=TT2[y];
m[{'C','T'}]=ct[y];
m[{'T','C'}]=tc[y];
m[{'A','T'}]=att[y];
m[{'T','A'}]=ta[y];
m[{'C','A'}]=ca[y];
m[{'A','C'}]=ac[y];
}
int we=0;
int ans=0;
if(A!=A2||C!=C2||T!=T2)
return -1;
else
{
int mn=min(m[{'A','T'}],m[{'T','A'}]); // cout<<" "<<mn<<endl;
ans-=mn*2; we+=mn; m[{'A','T'}]-=mn; m[{'T','A'}]-=mn;
mn=min(m[{'A','C'}],m[{'C','A'}]); //cout<<" "<<mn<<endl;
ans-=mn*2; we+=mn; m[{'A','C'}]-=mn; m[{'C','A'}]-=mn;
mn=min(m[{'T','C'}],m[{'C','T'}]); // cout<<" "<<mn<<endl;
m[{'T','C'}]-=mn; m[{'C','T'}]-=mn; //cout<<endl; cout<<endl;
ans-=mn*2; we+=mn;
int h=m[{'A','T'}];
h=max(h,m[{'T','A'}]);
h=max(h,m[{'A','C'}]);
h=max(h,m[{'C','A'}]);
h=max(h,m[{'T','C'}]);
h=max(h,m[{'C','T'}]);
we+=h*2;
} m.clear();
return we;
return 0;
}
// ATCTCAA TATCATC
