#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
const int nx = 1e5 + 5;
int qs[nx][2][3]; // 0 = A, 1 = T, 2 = C
int dp[nx][6]; // 0 = AT, 1 = TA, 2 = AC, 3 = CA, 4 = CT, 5 = TC
int n;
void init(std::string a, std::string b) {
n = a.size();
for (int i = 1; i <= n; i++) {
char x = a[i - 1], y = b[i - 1];
if (x == 'A') qs[i][0][0]++;
else if (x == 'T') qs[i][0][1]++;
else if (x == 'C') qs[i][0][2]++;
if (y == 'A') qs[i][1][0]++;
else if (y == 'T') qs[i][1][1]++;
else if (y == 'C') qs[i][1][2]++;
if (x == 'A' && y == 'T') dp[i][0]++;
else if (x == 'T' && y == 'A') dp[i][1]++;
else if (x == 'A' && y == 'C') dp[i][2]++;
else if (x == 'C' && y == 'A') dp[i][3]++;
else if (x == 'C' && y == 'T') dp[i][4]++;
else if (x == 'T' && y == 'C') dp[i][5]++;
qs[i][0][0] += qs[i-1][0][0];
qs[i][0][1] += qs[i-1][0][1];
qs[i][0][2] += qs[i-1][0][2];
qs[i][1][0] += qs[i-1][1][0];
qs[i][1][1] += qs[i-1][1][1];
qs[i][1][2] += qs[i-1][1][2];
dp[i][0] += dp[i-1][0];
dp[i][1] += dp[i-1][1];
dp[i][2] += dp[i-1][2];
dp[i][3] += dp[i-1][3];
dp[i][4] += dp[i-1][4];
dp[i][5] += dp[i-1][5];
//cout << qs[i][0][0] << " " << qs[i][1][0] << endl;
}
}
int get_distance(int x, int y) {
x++, y++;
//cout << endl;
//cout <<x << " - " << y << endl;
if (!(qs[y][0][0]-qs[x-1][0][0] == qs[y][1][0]-qs[x-1][1][0] &&
qs[y][0][1]-qs[x-1][0][1] == qs[y][1][1]-qs[x-1][1][1] &&
qs[y][0][2]-qs[x-1][0][2] == qs[y][1][2]-qs[x-1][1][2])) {
/*cout << qs[y][0][0]-qs[x-1][0][0] << " " << qs[y][1][0]-qs[x-1][1][0] << endl;
cout << qs[y][0][1]-qs[x-1][0][1] << " " << qs[y][1][1]-qs[x-1][1][1] << endl;
cout << qs[y][0][2]-qs[x-1][0][2] << " " << qs[y][1][2]-qs[x-1][1][2] << endl;*/
/*cout << qs[y][0][0] << " " << qs[y][1][0] << endl;
cout << qs[y][0][1] << " " << qs[y][1][1] << endl;
cout << qs[y][0][2] << " " << qs[y][1][2] << endl;*/
//cout << -1 << endl;
return -1;
}
int ans = 0;
// 0 = AT, 1 = TA, 2 = AC, 3 = CA, 4 = CT, 5 = TC
int p = 0, q = 0; // x = TA, y = TC;
// A + T
ans += min(dp[y][0]-dp[x-1][0], dp[y][1]-dp[x-1][1]);
if (dp[y][1]-dp[x-1][1] > dp[y][0]-dp[x-1][0]) p = (dp[y][1]-dp[x-1][1] - (dp[y][0]-dp[x-1][0]));
ans += min(dp[y][2]-dp[x-1][2], dp[y][3]-dp[x-1][3]);
ans += min(dp[y][4]-dp[x-1][4], dp[y][5]-dp[x-1][5]);
if (dp[y][5]-dp[x-1][5] > dp[y][4]-dp[x-1][4]) q = (dp[y][5]-dp[x-1][5] - (dp[y][4]-dp[x-1][4]));
ans += ((p + q) << 1);
//cout << p << " " << q << " " << ans << endl;
return ans;
}
/*
g++ grader.cpp dna.cpp -o o
6 3
ATACAT
ACTATA
1 3
4 5
3 5
2
1
-1
*/
