#include "dna.h"
#include<bits/stdc++.h>
using namespace std;
template<typename T>
using vec = vector<T>;
using ll = long long;
using str = string;
struct Ans {
ll A, T, C;
Ans() : A(0), T(0), C(0) {}
Ans(ll a, ll t, ll c) {
A = a; T = t; C = c;
}
bool operator!=(const Ans&two) const {
return not(A == two.A and T == two.T and C == two.C);
}
Ans operator+(const Ans&two) const {
return Ans(A+two.A, T+two.T, C+two.C);
}
Ans operator-(const Ans&two) const {
return Ans(A-two.A,T-two.T,C-two.C);
}
};
vec<Ans> aPref, bPref;
vec<vec<vec<ll>>> swaps; // swaps[i][a][b] = number of As that should swap to Bs
ll fuzz(char x) {
if(x == 'A') return 0;
if(x == 'T') return 1;
return 2;
}
ll n;
void init(str a, str b) {
n = a.length();
aPref.resize(n);
bPref.resize(n);
swaps.assign(n, vector<vector<ll>>(3, vector<ll>(3,0ll)));
for(int i = 0; i < n; i++) {
if(a[i] == 'A') aPref[i] = {1,0,0};
if(a[i] == 'T') aPref[i] = {0,1,0};
if(a[i] == 'C') aPref[i] = {0,0,1};
if(b[i] == 'A') bPref[i] = {1,0,0};
if(b[i] == 'T') bPref[i] = {0,1,0};
if(b[i] == 'C') bPref[i] = {0,0,1};
if(i) {
aPref[i] = aPref[i] + aPref[i-1];
bPref[i] = bPref[i] + bPref[i-1];
}
ll aa = fuzz(a[i]);
ll bb = fuzz(b[i]);
swaps[i][aa][bb] = 1;
// swaps[i][bb][aa] = 1;
if(i) {
for(int j = 0; j <= 2; j++) {
for(int k = 0; k <= 2; k++) {
swaps[i][j][k] += swaps[i-1][j][k];
}
}
}
}
}
int get_distance(int x, int y) {
Ans one = aPref[y] - (x ? aPref[x-1] : Ans(0,0,0));
Ans two = bPref[y] - (x ? bPref[x-1] : Ans(0,0,0));
if(one != two) return -1;
ll ans = 0;
bool flag = 0;
for(int i = 0; i <= 2; i++) {
for(int j = i+1; j <= 2; j++) {
ll bleh = swaps[y][i][j] - (x ? swaps[x-1][i][j] : 0);
ll blah = swaps[y][j][i] - (x ? swaps[x-1][j][i] : 0);
ans += min(bleh,blah);
if(bleh > blah and not flag) {
// then also need to make cyclic shift
// cyclic shift costs 2 * diff
ans += 2 * (bleh - blah);
flag = 1;
}
}
}
return ans;
}
/*(
ATACAT
ACTATA
TAC
CTA
)*/
