#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
int N;
vector<vector<int>> ps;
vector<int> ps_a, ps_t, ps_c;
string A, B;
void init(std::string a, std::string b)
{
int N = a.size();
A = a;
B = b;
// Construct prefix sums
ps = vector<vector<int>>(N+1, vector<int>(6));
for (int i = 0; i < N; i++)
{
for (int j = 0; j < 6; j++)
ps[i+1][j] = ps[i][j];
if (a[i] == 'A' && b[i] == 'T')
ps[i+1][0]++;
if (a[i] == 'A' && b[i] == 'C')
ps[i+1][1]++;
if (a[i] == 'C' && b[i] == 'T')
ps[i+1][2]++;
if (a[i] == 'T' && b[i] == 'A')
ps[i+1][3]++;
if (a[i] == 'C' && b[i] == 'A')
ps[i+1][4]++;
if (a[i] == 'T' && b[i] == 'C')
ps[i+1][5]++;
}
ps_a = ps_t = ps_c = vector<int>(N + 1);
for (int i = 0; i < N; i++)
ps_a[i+1] = ps_a[i] + (int)(a[i] == 'A') - (int)(b[i] == 'A');
for (int i = 0; i < N; i++)
ps_t[i+1] = ps_t[i] + (int)(a[i] == 'T') - (int)(b[i] == 'T');
for (int i = 0; i < N; i++)
ps_c[i+1] = ps_c[i] + (int)(a[i] == 'C') - (int)(b[i] == 'C');
}
int get_distance(int x, int y)
{
if (ps_a[y+1] - ps_a[x] != 0 || ps_t[y+1] - ps_t[x] != 0 || ps_c[y+1] - ps_c[x] != 0)
{
return -1;
}
vector<int> v(6);
for (int i = 0; i < 6; i++)
v[i] = ps[y+1][i] - ps[x][i];
int res = 0;
for (int i = 0; i < 3; i++)
{
int n = min(v[i], v[i+3]);
res += n;
v[i] -= n;
v[i+3] -= n;
}
if (v[0] + v[3] != v[1] + v[4] || v[0] + v[3] != v[2] + v[5])
return -1;
return res + (v[0] + v[3]) * 2;
}
