#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
string a, b;
vector<vector<int>> ama, amb;
vector<vector<vector<int>>> pref;
void init(std::string A, std::string B) {
a = A, b = B;
int n = a.size();
pref.assign(n, vector<vector<int>>(3, vector<int>(3, 0)));
ama.assign(n, vector<int>(3, 0));
amb = ama;
map<char, int> mp;
mp['A'] = 0;
mp['C'] = 1;
mp['T'] = 2;
for (int i=0; i<n; i++) {
for (int j=0; j<3; j++) {
for (int k=0; k<3; k++) {
int det = (i==0 ? 0 : pref[i-1][j][k]);
pref[i][j][k] = det;
}
}
if (a[i] != b[i]) {
pref[i][mp[a[i]]][mp[b[i]]]++;
}
for (int j=0; j<3; j++) {
int at = (i==0 ? 0 : ama[i-1][j]);
ama[i][j] = at;
at = (i==0 ? 0 : amb[i-1][j]);
amb[i][j] = at;
}
ama[i][mp[a[i]]]++;
amb[i][mp[b[i]]]++;
}
}
int get_distance(int x, int y) {
int det, A, B;
//calcular apariciones de A
det = (x==0 ? 0 : ama[x-1][0]);
A = ama[y][0] - det;
det = (x==0 ? 0 : amb[x-1][0]);
B = amb[y][0] - det;
if (A!=B) return -1;
//calcular apariciones de T
det = (x==0 ? 0 : ama[x-1][2]);
A = ama[y][2] - det;
det = (x==0 ? 0 : amb[x-1][2]);
B = amb[y][2] - det;
if (A!=B) return -1;
//calcular apariciones de C
det = (x==0 ? 0 : ama[x-1][1]);
A = ama[y][1] - det;
det = (x==0 ? 0 : amb[x-1][1]);
B = amb[y][1] - det;
if (A!=B) return -1;
vector<vector<int>> grid(3, vector<int>(3, 0));
for (int i=0; i<3; i++) {
for (int j=0; j<3; j++) {
det = (x==0 ? 0 : pref[x-1][i][j]);
grid[i][j] = pref[y][i][j] - det;
}
}
int ans=0;
for (int i=0; i<3; i++) {
for (int j=0; j<3; j++) {
if (i==j) continue;
//cout << i << " " << j << " " << grid[i][j] << " " << grid[j][i] << endl;
ans += min(grid[i][j], grid[j][i]);
int mn = min(grid[i][j], grid[j][i]);
grid[i][j] -= mn;
grid[j][i] -= mn;
}
}
int cnt=0;
bool entre=false;
int mn = 1e9;
for (int i=0; i<3; i++) {
for (int j=0; j<3; j++) {
if (grid[i][j] > 0) {
mn = min(mn, grid[i][j]);
entre = true;
}
cnt += grid[i][j];
}
}
if (entre) {
ans += cnt;
ans -= mn;
}
return ans;
}
