#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
string all = "ACT";
vector<int> A;
vector<int> C;
vector<int> T;
map<pair<char, char>, vector<int>> m;
void init(std::string a, std::string b){
A.resize(a.size()+1);
C.resize(a.size()+1);
T.resize(a.size()+1);
for(int i = 0; i < all.size(); i++){
for(int y = 0; y < all.size(); y++){
m[{all[i], all[y]}].resize(a.size()+1, 0);
}
}
for(int i = 1; i <= a.size(); i++){
if(a[i-1] == 'A'){
A[i]++;
}else if(a[i-1] == 'C'){
C[i]++;
}else{
T[i]++;
}
if(b[i-1] == 'A'){
A[i]--;
}else if(b[i-1] == 'C'){
C[i]--;
}else{
T[i]--;
}
A[i] += A[i-1];
C[i] += C[i-1];
T[i] += T[i-1];
m[{a[i-1], b[i-1]}][i]++;
for(int z = 0; z < all.size(); z++){
for(int y = 0; y < all.size(); y++){
m[{all[z], all[y]}][i] += m[{all[z], all[y]}][i-1];
}
}
}
}
int get_distance(int x, int y){
x++;
y++;
if(!(A[y] - A[x-1] == 0 && C[y] - C[x-1] == 0 && T[y] - T[x-1] == 0)){
return -1;
}
int ans = 0;
int cur = y-x+1;
cur -= m[{'A', 'A'}][y] - m[{'A', 'A'}][x-1];
cur -= m[{'T', 'T'}][y] - m[{'T', 'T'}][x-1];
cur -= m[{'C', 'C'}][y] - m[{'C', 'C'}][x-1];
for(int i = 0; i < all.size(); i++){
for(int z = i+1; z < all.size(); z++){
ans += min(m[{all[i], all[z]}][y] - m[{all[i], all[z]}][x-1], m[{all[z], all[i]}][y] - m[{all[z], all[i]}][x-1]);
cur -= 2*min(m[{all[i], all[z]}][y] - m[{all[i], all[z]}][x-1], m[{all[z], all[i]}][y] - m[{all[z], all[i]}][x-1]);
}
}
ans += cur/3*2;
return ans;
}
