#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<int> pref;
void init(std::string A, std::string B) {
a = A, b = B;
int n = a.size();
pref.assign(n, 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++) {
int at = (i==0 ? 0 : pref[i-1]);
pref[i] = at + (a[i]!=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) {
map<char, int> mp1, mp2;
map<char, int> mp;
mp['A'] = 0;
mp['C'] = 1;
mp['T'] = 2;
vector<vector<int>> grid(3, vector<int>(3, 0));
for (int i=x; i<=y; i++) {
mp1[a[i]]++;
mp2[b[i]]++;
if (a[i] != b[i]) {
grid[mp[a[i]]][mp[b[i]]]++;
}
}
if (mp1 != mp2) return -1;
int ans=0;
for (int i=0; i<3; i++) {
for (int j=0; j<3; j++) {
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;
for (int i=0; i<3; i++) {
for (int j=0; j<3; j++) {
cnt += grid[i][j];
}
}
return ans+(cnt+1)/2;
}
