#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
#define fi first
#define se second
#define pb push_back
#define sz(a) (ll) a.size()
#define all(x) (x).begin(), (x).end()
#define rep(i, a, b) for (ll i = a; i < b; i++)
#define rrep(i, a, b) for (ll i = a; i >= b; i--)
#define vl vector<ll>
#define vpll vector<pair<ll, ll>>
#define vvl vector<vector<ll>>
#define pll pair<ll, ll>
vl closest_ok, cnt;
void init(std::string a, std::string b) {
map<pair<ll, pair<ll, ll>>, ll> mp;
mp[{0, {0, 0}}] = 0;
closest_ok.assign(a.size(), -2);
cnt.assign(a.size(), -2);
ll aa = 0, bb = 0, cc = 0;
rep(i, 0, a.size()) {
if (a[i] == 'C') aa++;
if (a[i] == 'A') bb++;
if (a[i] == 'T') cc++;
if (b[i] == 'C') aa--;
if (b[i] == 'A') bb--;
if (b[i] == 'T') cc--;
if (mp.find({aa, {bb, cc}}) != mp.end()) {
closest_ok[mp[{aa, {bb, cc}}]] = i;
}
mp[{aa, {bb, cc}}] = i + 1;
}
rep(i, 0, sz(a)){
if(closest_ok[i]==-2) continue;
cnt[i]=0;
if(a[i]==b[i]) continue;
vvl v(3, vl(3, 0));
rep(j, i, closest_ok[i]+1){
if(closest_ok[j]!=-2 && closest_ok[j]<=closest_ok[i] && j!=i){
j=closest_ok[j];
cnt[i]+=cnt[j];
continue;
}
if(a[j]=='C') aa=0;
if(a[j]=='A') aa=1;
if(a[j]=='T') aa=2;
if(b[j]=='C') bb=0;
if(b[j]=='A') bb=1;
if(b[j]=='T') bb=2;
v[aa][bb]++;
}
rep(j, 0, 3){
rep(k, 0, 3){
int dist=min(v[j][k],v[k][j]);
v[j][k]-=dist;
v[k][j]-=dist;
cnt[i]+=dist;
}
}
cnt[i]+=(v[0][1]+v[0][2])*2;
}
}
int get_distance(int x, int y) {
int can = x; int ans=0;
while(can<=y && can!=-1){
ans+=cnt[can];
can=closest_ok[can]+1;
}
if(can==y+1) return ans;
else return -1;
}
