#include "dna.h"
#include <bits/stdc++.h>
#define endl "\n"
#define ff first
#define ss second
#define pb push_back
#define all(v) v.begin(), v.end()
using namespace std;
map <char, int> m;
vector <int> pra[3], prb[3];
vector <int> ac, at, ta, tc, ca, ct;
void init(string a, string b) {
int n = a.size();
m['A'] = 0;
m['T'] = 1;
m['C'] = 2;
for (int i = 0; i < 3; i++) {
pra[i].pb(m[a[0]] == i);
prb[i].pb(m[b[0]] == i);
}
for (int i = 1; i < n; i++) {
for (int j = 0; j < 3; j++) pra[j].pb(pra[j][i-1]), prb[j].pb(prb[j][i-1]);
pra[m[a[i]]][i]++;
prb[m[b[i]]][i]++;
}
ac.pb((a[0] == 'A' && b[0] == 'C' ? 1 : 0));
ta.pb((a[0] == 'T' && b[0] == 'A' ? 1 : 0));
at.pb((a[0] == 'A' && b[0] == 'T' ? 1 : 0));
tc.pb((a[0] == 'T' && b[0] == 'C' ? 1 : 0));
ca.pb((a[0] == 'C' && b[0] == 'A' ? 1 : 0));
ct.pb((a[0] == 'C' && b[0] == 'T' ? 1 : 0));
for (int i = 1; i < n; i++) {
ac.pb(ac.back());
ta.pb(ta.back());
at.pb(at.back());
tc.pb(tc.back());
ca.pb(ca.back());
ct.pb(ct.back());
if (a[i] == 'A' && b[i] == 'C') ac[i]++;
if (a[i] == 'T' && b[i] == 'A') ta[i]++;
if (a[i] == 'A' && b[i] == 'T') at[i]++;
if (a[i] == 'T' && b[i] == 'C') tc[i]++;
if (a[i] == 'C' && b[i] == 'A') ca[i]++;
if (a[i] == 'C' && b[i] == 'T') ct[i]++;
}
}
int f(int &a, int &b) {
int x = min(a, b);
a -= x;
b -= x;
return x;
}
int get_distance(int l, int r) {
for (int i = 0; i < 3; i++) {
int c1 = pra[i][r] - (l == 0 ? 0 : pra[i][l-1]);
int c2 = prb[i][r] - (l == 0 ? 0 : prb[i][l-1]);
cerr << c1 << ' ' << c2 << endl;
if (c1 != c2) return -1;
}
int AT = at[r] - (l == 0 ? 0 : at[l-1]);
int TA = ta[r] - (l == 0 ? 0 : ta[l-1]);
int AC = ac[r] - (l == 0 ? 0 : ac[l-1]);
int TC = tc[r] - (l == 0 ? 0 : tc[l-1]);
int CA = ca[r] - (l == 0 ? 0 : ca[l-1]);
int CT = ct[r] - (l == 0 ? 0 : ct[l-1]);
int res = 0;
res += f(AT, TA);
res += f(AC, CA);
res += f(TC, CT);
if (AT == TC && TC == CA && AC == TA && TA == CT) {
res += AT * 2 + AC * 2;
}
else return -1;
return res;
}
