#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
map <char, vector <int>> pfxa, pfxb;
map <string, vector <int>> pfx;
int n;
vector <char> tp = {'A', 'T', 'C'};
vector <string> tp2 = {"AC", "CA", "TA", "AT", "CT", "TC"};
void init(std::string a, std::string b) {
n = a.size();
for (auto i : tp)
pfxa[i] = pfxb[i] = vector <int> (n+5);
for (auto i : tp2)
pfx[i] = vector <int> (n + 5);
for (int i = 0; i < n; i++) {
pfxa[a[i]][i]++;
pfxb[b[i]][i]++;
string tp3; tp3.resize(2);
tp3[0] = a[i]; tp3[1] = b[i];
if (a[i] != b[i])
pfx[tp3][i]++;
if (i > 0) {
for (auto j : tp) {
pfxa[j][i] += pfxa[j][i-1];
pfxb[j][i] += pfxb[j][i-1];
}
for (auto j : tp2) {
pfx[j][i] += pfx[j][i-1];
}
}
}
}
int get_distance(int x, int y) {
for (auto i : tp) {
int s1 = pfxa[i][y];
int s2 = pfxb[i][y];
if (x > 0) {
s1 -= pfxa[i][x-1];
s2 -= pfxb[i][x-1];
}
if (s1 != s2)
return -1;
}
int ans = 0;
int cnt = pfx["AC"][y];
if (x > 0)
cnt -= pfx["AC"][x-1];
int cnt2 = pfx["CA"][y];
if (x > 0)
cnt2 -= pfx["CA"][x-1];
ans += abs(cnt - cnt2) * 3;
ans += min(cnt, cnt2);
cnt = pfx["AT"][y];
if (x > 0)
cnt -= pfx["AT"][x-1];
cnt2 = pfx["TA"][y];
if (x > 0)
cnt2 -= pfx["TA"][x-1];
ans += min(cnt, cnt2);
cnt = pfx["CT"][y];
if (x > 0)
cnt -= pfx["CT"][x-1];
cnt2 = pfx["TC"][y];
if (x > 0)
cnt2 -= pfx["TC"][x-1];
ans += min(cnt, cnt2);
return ans;
}
