#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
vector <int> ca, cb, aa, ab, ta, tb;
vector <int> AC, CA, CT, TC, AT, TA;
vector <int> cor;
int n;
void init(string a, string b) {
n = a.size();
ca.resize(n, 0);
cb.resize(n, 0);
aa.resize(n, 0);
ab.resize(n, 0);
ta.resize(n, 0);
tb.resize(n, 0);
AC.resize(n, 0);
CA.resize(n, 0);
CT.resize(n, 0);
TC.resize(n, 0);
AT.resize(n, 0);
TA.resize(n, 0);
cor.resize(n, 0);
if (a[0] == 'A') {
aa[0] = 1;
if (b[0] == 'C') {
AC[0]++;
}
if (b[0] == 'T') {
AT[0]++;
}
}
if (a[0] == 'T') {
ta[0] = 1;
if (b[0] == 'C') {
TC[0]++;
}
if (b[0] == 'A') {
TA[0]++;
}
}
if (a[0] == 'C') {
ca[0] = 1;
if (b[0] == 'A') {
CA[0]++;
}
if (b[0] == 'T') {
CT[0]++;
}
}
if (b[0] == 'A') ab[0] = 1;
if (b[0] == 'T') tb[0] = 1;
if (b[0] == 'C') cb[0] = 1;
for (int i = 1;i < n;i++) {
CA[i] = CA[i - 1];
TA[i] = TA[i - 1];
AC[i] = AC[i - 1];
TC[i] = TC[i - 1];
CT[i] = CT[i - 1];
AT[i] = AT[i - 1];
if (a[i] == 'A') {
aa[i] = aa[i - 1] + 1;
if (b[i] == 'C') {
AC[i]++;
}
if (b[i] == 'T') {
AT[i]++;
}
}
else aa[i] = aa[i - 1];
if (a[i] == 'T') {
ta[i] = ta[i - 1] + 1;
if (b[i] == 'C') {
TC[i]++;
}
if (b[i] == 'A') {
TA[i]++;
}
}
else ta[i] = ta[i - 1];
if (a[i] == 'C') {
ca[i] = ca[i - 1] + 1;
if (b[i] == 'A') {
CA[i]++;
}
if (b[i] == 'T') {
CT[i]++;
}
}
else ca[i] = ca[i - 1];
if (b[i] == 'A') ab[i] = ab[i - 1] + 1;
else ab[i] = ab[i - 1];
if (b[i] == 'T') tb[i] = tb[i - 1] + 1;
else tb[i] = tb[i - 1];
if (b[i] == 'C') cb[i] = cb[i - 1] + 1;
else cb[i] = cb[i - 1];
}
for (int i = 0;i < n;i++) {
if (i != 0) cor[i] = cor[i - 1];
if (a[i] == b[i]) {
cor[i]++;
}
}
}
int get_distance(int x, int y) {
if (x == 0) {
if (ca[y] != cb[y] ) {
return -1;
}
if (ta[y] != tb[y]) {
return -1;
}
if (aa[y] != ab[y]) {
return -1;
}
int cnt = y + 1;
int res = 0;
cnt -= cor[y];
res += min(CA[y], AC[y]);
res += min(TA[y], AT[y]);
// cout << TA[y] << ' ' << AT[y] << endl;
res += min(TC[y], CT[y]);
cnt -= res * 2;
res += cnt / 3 * 2;
// cout << cor[y] << ' ' << cnt << ' ' << res << endl;
return res;
}
if (ca[y] - ca[x - 1] != cb[y] - cb[x - 1]) {
return -1;
}
if (ta[y] - ta[x - 1] != tb[y] - tb[x - 1]) {
return -1;
}
if (aa[y] - aa[x - 1] != ab[y] - ab[x - 1]) {
return -1;
}
int cnt = y - x + 1;
int res = 0;
cnt -= cor[y] - cor[x - 1];
res += min(CA[y] - CA[x - 1], AC[y] - AC[x - 1]);
res += min(TA[y] - TA[x - 1], AT[y] - AT[x - 1]);
res += min(TC[y] - TC[x - 1], CT[y] - CT[x - 1]);
cnt -= res * 2;
res += cnt / 3 * 2;
// cout << cor[y] << ' ' << cnt << endl;
return res;
return 0;
}
