#include "dna.h"
using namespace std;
const int N = 1e5 + 10;
int p[N][6], cnta[N][3], cntb[N][3];
//0 - AT
//1 - TA
//2 - AC
//3 - CA
//4 - TC
//5 - CT
//0 - A
//1 - C
//2 - T
void init(std::string a, std::string b) {
int n = a.size();
for(int i = 1; i <= n; ++i) {
for(int j = 0; j < 6; ++j) p[i][j] = p[i - 1][j];
if(a[i - 1] == 'A' && b[i - 1] == 'T') ++p[i][0];
if(a[i - 1] == 'T' && b[i - 1] == 'A') ++p[i][1];
if(a[i - 1] == 'A' && b[i - 1] == 'C') ++p[i][2];
if(a[i - 1] == 'C' && b[i - 1] == 'A') ++p[i][3];
if(a[i - 1] == 'T' && b[i - 1] == 'C') ++p[i][4];
if(a[i - 1] == 'C' && b[i - 1] == 'T') ++p[i][5];
for(int j = 0; j < 3; ++j) cnta[i][j] = cnta[i - 1][j], cntb[i][j] = cntb[i - 1][j];
if(a[i - 1] == 'A') cnta[i][0]++;
else if(a[i - 1] == 'C') cnta[i][1]++;
else cnta[i][2]++;
if(b[i - 1] == 'A') cntb[i][0]++;
else if(b[i - 1] == 'C') cntb[i][1]++;
else cntb[i][2]++;
}
}
//0 - AT
//1 - TA
//2 - AC
//3 - CA
//4 - TC
//5 - CT
//0 - A
//1 - C
//2 - T
int get_distance(int x, int y) {
++x, ++y;
int AT = p[y][0] - p[x - 1][0], TA = p[y][1] - p[x - 1][1], AC = p[y][2] - p[x - 1][2];
int CA = p[y][3] - p[x - 1][3], TC = p[y][4] - p[x - 1][4], CT = p[y][5] - p[x - 1][5];
for(int j = 0; j < 3; ++j) if(cnta[y][j] - cnta[x - 1][j] != cntb[y][j] - cntb[x - 1][j]) return -1;
int ans = 0;
int f = min(AT, TA); ans += f;
AT -= f, TA -= f;
f = min(AC, CA); ans += f;
AC -= f, CA -= f;
f = min(TC, CT); ans += f;
TC -= f, CT -= f;
ans += (AT + TA + AC + CA + TC + CT) / 3 * 2;
return ans;
}
/*
6 3
ATACAT
ACTATA
1 3
4 5
3 5
*/
