#include "dna.h"
#include "bits/stdc++.h"
using namespace std;
int a[100005][6], cnta[100005][3], cntb[100005][3] /* AC, AT, CA, CT, TA, TC */;
void init(string A, string B)
{
for(int i=0; i<(int)A.length(); i++)
{
if(A[i]=='A' and B[i]=='C') a[i+1][0]=1;
if(A[i]=='A' and B[i]=='T') a[i+1][1]=1;
if(A[i]=='C' and B[i]=='A') a[i+1][2]=1;
if(A[i]=='C' and B[i]=='T') a[i+1][3]=1;
if(A[i]=='T' and B[i]=='A') a[i+1][4]=1;
if(A[i]=='T' and B[i]=='C') a[i+1][5]=1;
for(int j=0; j<6; j++)
a[i+1][j]+=a[i][j];
if(A[i]=='A') cnta[i+1][0]=1;
if(A[i]=='C') cnta[i+1][1]=1;
if(A[i]=='T') cnta[i+1][2]=1;
if(B[i]=='A') cntb[i+1][0]=1;
if(B[i]=='C') cntb[i+1][1]=1;
if(B[i]=='T') cntb[i+1][2]=1;
cnta[i+1][0]+=cnta[i][0];
cnta[i+1][1]+=cnta[i][1];
cnta[i+1][2]+=cnta[i][2];
cntb[i+1][0]+=cntb[i][0];
cntb[i+1][1]+=cntb[i][1];
cntb[i+1][2]+=cntb[i][2];
}
}
int get_distance(int x, int y)
{
if(cnta[y+1][0]-cnta[x][0]!=cntb[y+1][0]-cntb[x][0] or
cnta[y+1][1]-cnta[x][1]!=cntb[y+1][1]-cntb[x][1] or
cnta[y+1][2]-cnta[x][2]!=cntb[y+1][2]-cntb[x][2]) return -1;
int num=0, ans=0, k;
k=min(a[y+1][0]-a[x][0], a[y+1][2]-a[x][2]);
num+=k;
ans+=a[y+1][0]-a[x][0]-k;
ans+=a[y+1][2]-a[x][2]-k;
k=min(a[y+1][1]-a[x][1], a[y+1][4]-a[x][4]);
num+=k;
ans+=a[y+1][1]-a[x][1]-k;
ans+=a[y+1][4]-a[x][4]-k;
k=min(a[y+1][3]-a[x][3], a[y+1][5]-a[x][5]);
num+=k;
ans+=a[y+1][3]-a[x][3]-k;
ans+=a[y+1][5]-a[x][5]-k;
return num+ans/3*2;
}
/*
6 3
ATACAT
ACTATA
1 3
4 5
3 5
*/
