/**
____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|
**/
#include <bits/stdc++.h>
#include "dna.h"
using namespace std;
typedef long long ll;
int encode (char c)
{
if(c == 'A')
return 0;
if(c == 'C')
return 1;
if(c == 'T')
return 2;
assert(false);
}
vector <vector <vector <int>>> cntPref;
void init (string a, string b)
{
int n = (int) a.size();
cntPref = vector <vector <vector <int>>> (n, vector <vector <int>> (3, vector <int> (3)));
for(int i = 0; i < n; i++)
{
if(i - 1 >= 0)
cntPref[i] = cntPref[i - 1];
cntPref[i][encode(a[i])][encode(b[i])]++;
}
}
int get_distance (int x, int y)
{
vector <vector <int>> cnt = cntPref[y];
if(x - 1 >= 0)
{
for(int u = 0; u < 3; u++)
for(int v = 0; v < 3; v++)
cnt[u][v] -= cntPref[x - 1][u][v];
}
vector <int> cnta (3);
vector <int> cntb (3);
for(int u = 0; u < 3; u++)
for(int v = 0; v < 3; v++)
{
cnta[u] += cnt[u][v];
cntb[v] += cnt[u][v];
}
for(int u = 0; u < 3; u++)
if(cnta[u] != cntb[u])
return -1;
int answer = 0;
for(int u = 0; u < 3; u++)
cnt[u][u] = 0;
for(int u = 0; u < 3; u++)
for(int v = u + 1; v < 3; v++)
{
int take = min(cnt[u][v], cnt[v][u]);
answer += take;
cnt[u][v] -= take;
cnt[v][u] -= take;
}
int sum = 0;
for(int u = 0; u < 3; u++)
for(int v = 0; v < 3; v++)
sum += cnt[u][v];
answer += sum / 3 * 2;
return answer;
}
