// SUBTASK 1 -> 5
#include <bits/stdc++.h>
#include "dna.h"
//#include "grader.cpp"
using namespace std;
string a, b;
vector <vector<int>> pref_a;
vector <vector<int>> pref_b;
vector <vector<int>> cnt(3, vector<int>(3));
vector <vector<vector<int>>> pref;
int id(char ch)
{
if (ch == 'A') return 0;
if (ch == 'T') return 1;
return 2; // C
}
void init(string A, string B)
{
a = A;
b = B;
int n = a.size();
pref.resize(n, vector<vector<int>>(3, vector<int>(3)));
for (int i = 0; i < n; i++)
{
if (i > 0) pref[i] = pref[i - 1];
int id1 = id(a[i]), id2 = id(b[i]);
if (id1 != id2) pref[i][id1][id2]++;
}
}
bool validate(int x, int y)
{
for (int i = 0; i < 3; i++)
{
int in = 0, out = 0;
for (int j = 0; j < 3; j++)
{
in += cnt[i][j];
out += cnt[j][i];
}
if (in != out) return false;
}
return true;
}
void build_local_matrix(int x, int y)
{
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
cnt[i][j] = x > 0 ? pref[y][i][j] - pref[x - 1][i][j] : pref[y][i][j];
}
}
}
int get_distance(int x, int y)
{
build_local_matrix(x, y);
if (!validate(x, y)) return -1;
int ans = 0, remain = 0;
for (int i = 0; i < 3; i++)
{
for (int j = i + 1; j < 3; j++)
{
int swaps = min(cnt[i][j], cnt[j][i]);
ans += swaps;
remain += max(cnt[i][j], cnt[j][i]) - swaps;
}
}
ans += (remain / 3) * 2;
return ans;
}
/*
6 3
ATACAT
ACTATA
1 3
4 5
3 5
2
1
-1
2 1
AA
TT
0 1
*/
