#include <iostream>
#include <array>
#include "dna.h"
#define ll long long
using namespace std;
array<ll, 6> st[400000], Q;
string S, T, D[6] = {"AT", "AC", "TC", "CT", "CA", "TA"};
ll n, f, z, C[26], R[6], mx;
void build(ll id, ll l, ll r) {
if (l == r) {
for (int i=0; i<6; ++i) {
if (D[i][0] == S[l] && D[i][1] == T[l]) {
++st[id][i];
break;
}
}
return;
}
ll mid = (l+r)/2, z;
build(id*2, l, mid);
build(id*2+1, mid+1, r);
st[id] = st[id*2];
for (int i=0; i<6; ++i) {
st[id][i] += st[id*2+1][i];
}
}
void query(ll id, ll l, ll r, ll ql, ll qr) {
if (r < ql || qr < l) return;
else if (ql <= l && r <= qr) {
for (int i=0; i<6; ++i) {
Q[i] += st[id][i];
}
return;
}
ll mid = (l+r)/2;
query(id*2, l, mid, ql, qr);
query(id*2+1, mid+1, r, ql, qr);
}
void init(std::string a, std::string b) {
S = a, T = b;
n = a.size();
C['A'-'A'] = 0, C['T'-'A'] = 1, C['C'-'A'] = 2;
build(1, 0, n-1);
}
int get_distance(int x, int y) {
for (int i=0; i<6; ++i) R[i] = Q[i] = 0;
f = mx = 0;
query(1, 0, n-1, x, y);
for (int i=0; i<3; ++i) {
z = min(Q[i], Q[5-i]);
Q[i] -= z, Q[5-i] -= z;
f += z;
}
for (int i=0; i<6; ++i) {
mx = max(mx, Q[i]);
for (int j=0; j<2; ++j) {
R[C[D[i][j]-'A']+j*3] += Q[i];
}
}
for (int i=0; i<3; ++i) {
if (R[i] != R[i+3]) return -1;
}
return f+mx*2;
}
