#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;
vector<vvl> mis, no;
void init(std::string a, std::string b) {
no.assign(2, vvl(sz(a), vl(3, 0)));
mis.assign(a.size(), vvl(3, vl(3, 0)));
rep(i, 0, sz(a)){
if(i!=0) mis[i]=mis[i-1];
if(i!=0){
no[0][i]=no[0][i-1];
no[1][i]=no[1][i-1];
}
if(a[i]==b[i]) continue;
int aa=0, bb=0;
if(a[i]=='A') aa=1;
if(a[i]=='T') aa=2;
if(b[i]=='A') bb=1;
if(b[i]=='T') bb=2;
no[0][i][aa]++;
no[1][i][bb]++;
mis[i][aa][bb]++;
}
}
int get_distance(int x, int y) {
vvl cnt=mis[y];
if(x!=0){
rep(i, 0, 3){
if(no[0][y][i]-no[0][x-1][i]!=no[1][y][i]-no[1][x-1][i]){
return -1;
}
rep(j, 0, 3){
cnt[i][j]-=mis[x-1][i][j];
}
}
} else {
rep(i, 0, 3){
if(no[0][y][i]!=no[1][y][i]){
return -1;
}
}
}
ll ans=0;
rep(i, 0, 3){
rep(j, 0, 3){
ll dist=min(cnt[i][j], cnt[j][i]);
ans+=dist;
cnt[i][j]-=dist;
cnt[j][i]-=dist;
}
}
ans+=(cnt[0][1]+cnt[0][2])*2;
return ans;
}
