#include "dna.h"
#include <bits/stdc++.h>
int N;
int *anumA, *anumT, *anumC;
int *bnumA, *bnumT, *bnumC;
int *diff;
int *dats, *dacs, *dtas, *dtcs, *dcas, *dcts;
std::string A, B;
void init(std::string _a, std::string _b) {
A = std::move(_a);
B = std::move(_b);
N = A.size();
for (auto x: {&anumA, &anumT, &anumC, &bnumA, &bnumT, &bnumC, &diff, &dats, &dacs, &dtas, &dtcs, &dcas, &dcts}) {
*x = new int[N];
}
anumA[0] = A[0] == 'A';
anumT[0] = A[0] == 'T';
anumC[0] = A[0] == 'C';
bnumA[0] = B[0] == 'A';
bnumT[0] = B[0] == 'T';
bnumC[0] = B[0] == 'C';
diff[0] = A[0] != B[0];
dats[0] = (A[0] == 'A' && B[0] == 'T');
dacs[0] = (A[0] == 'A' && B[0] == 'C');
dtas[0] = (A[0] == 'T' && B[0] == 'A');
dtcs[0] = (A[0] == 'T' && B[0] == 'C');
dcas[0] = (A[0] == 'C' && B[0] == 'A');
dcts[0] = (A[0] == 'C' && B[0] == 'T');
for (int i = 1; i < N; ++i) {
anumA[i] = anumA[i - 1] + (A[i] == 'A');
anumT[i] = anumT[i - 1] + (A[i] == 'T');
anumC[i] = anumC[i - 1] + (A[i] == 'C');
bnumA[i] = bnumA[i - 1] + (B[i] == 'A');
bnumT[i] = bnumT[i - 1] + (B[i] == 'T');
bnumC[i] = bnumC[i - 1] + (B[i] == 'C');
diff[i] = diff[i - 1] + (A[i] != B[i]);
dats[i] = dats[i - 1] + (A[i] == 'A' && B[i] == 'T');
dacs[i] = dacs[i - 1] + (A[i] == 'A' && B[i] == 'C');
dtas[i] = dtas[i - 1] + (A[i] == 'T' && B[i] == 'A');
dtcs[i] = dtcs[i - 1] + (A[i] == 'T' && B[i] == 'C');
dcas[i] = dcas[i - 1] + (A[i] == 'C' && B[i] == 'A');
dcts[i] = dcts[i - 1] + (A[i] == 'C' && B[i] == 'T');
}
}
int num(int *data, int l, int r) {
int x = data[r];
if (l) x -= data[l - 1];
return x;
}
int get_distance(int x, int y) {
int aa = num(anumA, x, y);
int ba = num(bnumA, x, y);
int at = num(anumT, x, y);
int bt = num(bnumT, x, y);
int ac = num(anumC, x, y);
int bc = num(bnumC, x, y);
if (aa != ba || at != bt || ac != bc) return -1;
if (y - x <= 2) {//Subtask 1
int d = 0;
for (int i = x; i <= y; ++i) {
d += A[i] != B[i];
}
return (d + 1) / 2;
}
if ((ac == 0 && bc == 0) || (aa == 0 && ba == 0) || (at == 0 && bt == 0)) {
return num(diff, x, y) / 2;
}
int dac = num(dacs, x, y);
int dat = num(dats, x, y);
int dta = num(dtas, x, y);
int dtc = num(dtcs, x, y);
int dca = num(dcas, x, y);
int dct = num(dcts, x, y);
int groupA = dac - dca;
assert(groupA == dta - dat);
assert(groupA == dct - dtc);
int ans = 0;
if (groupA > 0) {
ans = 2 * groupA;
dac -= groupA;
dct -= groupA;
dta -= groupA;
} else if (groupA < 0) {
ans = -2 * groupA;
dca += groupA;
dtc += groupA;
dat += groupA;
}
assert(dac == dca);
assert(dat == dta);
assert(dct == dtc);
ans += dac + dat + dct;
return ans;
}
