#include "dna.h"
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;
const int N = 1e5 + 5;
int p[9][N], ha[3][N], hb[3][N], n;
vector <string> v;
void init(string a, string b) {
string tmp = "ACT";
for (char a : tmp) {
for (char b : tmp) {
string res;
res.push_back(a);
res.push_back(b);
v.push_back(res);
}
}
sort(all(v));
n = a.size();
a = "1" + a;
b = "1" + b;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < 3; j++)
ha[j][i] = ha[j][i - 1], hb[j][i] = hb[j][i - 1];
ha[lower_bound(all(tmp), a[i]) - tmp.begin()][i]++;
hb[lower_bound(all(tmp), b[i]) - tmp.begin()][i]++;
for (int j = 0; j < 9; j++)
p[j][i] = p[j][i - 1];
string temp;
temp.push_back(a[i]);
temp.push_back(b[i]);
int k = lower_bound(all(v), temp) - v.begin();
p[k][i]++;
}
}
int get_distance(int x, int y) {
swap(x, y);
x++, y++;
for (int i = 0; i < 3; i++)
if (ha[i][x] - ha[i][y - 1] != hb[i][x] - hb[i][y - 1])
return -1;
vector <int> cnt(9);
int len = x - y + 1, ans = 0;
for (int i = 0; i < 9; i++) {
cnt[i] = p[i][x] - p[i][y - 1];
if (i % 3 == i / 3)
len -= cnt[i], cnt[i] = 0;;
}
string tmp = "ACT";
for (int i = 0; i < 3; i++) {
for (int j = i + 1; j < 3; j++) {
string ta, tb;
ta.push_back(tmp[i]);
ta.push_back(tmp[j]);
tb.push_back(tmp[j]);
tb.push_back(tmp[i]);
int ka = lower_bound(all(v), ta) - v.begin();
int kb = lower_bound(all(v), tb) - v.begin();
int mn = min(cnt[ka], cnt[kb]);
ans += mn;
len -= mn << 1;
}
}
return ans + len / 3 * 2;
}
