#include <bits/stdc++.h>
#define ll long long
#define i128 __int128_t
#define pii pair<int, int>
#define oo 1e9
#define table array<array<int, 3>, 3>
using namespace std;
int n = 0;
string a, b;
vector<table> tree;
table combine(table t1, table t2){
table ans;
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
ans[i][j] = t1[i][j] + t2[i][j];
}
}
return ans;
}
void build(int node, int l, int r){
if(l == r){
tree[node][a[l]][b[l]] = 1;
return;
}
int mid = (l + r) / 2;
build(node * 2 + 1, l, mid);
build(node * 2 + 2, mid + 1, r);
tree[node] = combine(tree[node * 2 + 1], tree[node * 2 + 2]);
}
table ask(int node, int l, int r, int ql, int qr){
if(qr < l || r < ql){
return table();
}
else if(ql <= l && r <= qr){
return tree[node];
}
int mid = (l + r) / 2;
return combine(ask(node * 2 + 1, l, mid, ql, qr), ask(node * 2 + 2, mid + 1, r, ql, qr));
}
void init(string s1, string s2){
a = s1;
b = s2;
n = a.size();
map<char,char> m = {{'A', 0}, {'C', 1}, {'T', 2}};
for (int i = 0; i < n; i++)
{
a[i] = m[a[i]];
b[i] = m[b[i]];
}
tree.resize(n * 4);
build(0, 0, n - 1);
}
int get_distance(int x, int y){
int ans = 0;
int c = 0;
table t = ask(0, 0, n - 1, x, y);
for (int i = 0; i < 3; i++) t[i][i] = 0;
int s = 0;
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
if(i == j) continue;
int a = min(t[i][j], t[j][i]);
ans += a;
t[i][j] -= a;
t[j][i] -= a;
s += t[i][j];
}
}
for (int i = 0; i < 3; i++)
{
int a = 0, b = 0;
for (int j = 0; j < 3; j++)
{
a += t[i][j];
b += t[j][i];
}
if(a != b){
return -1;
}
}
ans += s / 3 * 2;
return ans;
}
