#include <bits/stdc++.h>
using namespace std;
#include "dna.h"
#define tii array<array<int,3>, 3>
tii operator+(const tii &x, const tii &y) {
tii res;
for (int i=0;i<3;i++)
for (int j=0;j<3;j++)
res[i][j] = x[i][j] + y[i][j];
return res;
}
tii operator-(const tii &x, const tii &y) {
tii res;
for (int i=0;i<3;i++)
for (int j=0;j<3;j++)
res[i][j] = x[i][j] - y[i][j];
return res;
}
void print(tii arr) {
for (int i=0;i<3;i++) {
for (int j=0;j<3;j++)
cout << arr[i][j] << " ";
cout << endl;
}
cout << endl;
}
int conv(char c) {
if (c == 'A') return 0;
else if (c == 'T') return 1;
return 2;
}
vector<tii> p;
void init(string a, string b) {
int n = (int)a.size();
p.resize(n + 1);
for (int i=0;i<3;i++)
for (int j=0;j<3;j++)
p[0][i][j] = 0;
p[0][conv(a[0])][conv(b[0])]++;
for (int i=1;i<n;i++) {
p[i] = p[i-1];
p[i][conv(a[i])][conv(b[i])]++;
}
}
int get_distance(int x, int y) {
tii arr = p[y];
if (x) {
arr = arr - p[x-1];
}
int result = 0;
for (int i=0;i<3;i++) arr[i][i] = 0;
for (int i=0;i<3;i++) {
for (int j=0;j<3;j++) {
int mn = min(arr[i][j], arr[j][i]);
result += mn;
arr[i][j] -= mn;
arr[j][i] -= mn;
}
}
for (int i=0;i<3;i++) {
for (int j=0;j<3;j++) {
if (arr[i][j] == 0) continue;
int other = 3 - i - j;
int mn = min(arr[i][j], min(arr[j][other], arr[other][i]));
arr[i][j] -= mn;
arr[j][other] -= mn;
arr[other][i] -= mn;
result += 2*mn;
}
}
for (int i=0;i<3;i++) {
for (int j=0;j<3;j++) {
if (arr[i][j]) return -1;
}
}
return result;
}
