#include <bits/stdc++.h>
#include "dna.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define LSOne(S) ((S) & -(S))
struct Fenwick {
vector<int> ft;
Fenwick(int n) : ft(n+1, 0) {}
int qry(int i) {
int su = 0;
for (; i > 0; i -= LSOne(i)) {
su += ft[i];
}
return su;
}
int qry(int i, int j) {
return qry(j)-qry(i-1);
}
void upd(int i, int dv) {
for (; i < (int)ft.size(); i += LSOne(i)) {
ft[i] += dv;
}
}
};
map<char, int> cmap = {
{'A', 0},
{'T', 1},
{'C', 2}
};
vector<Fenwick> o1;
vector<Fenwick> o2;
vector<Fenwick> ts;
void init(string a, string b) {
int n = a.size();
o1.assign(3, Fenwick(n));
o2.assign(3, Fenwick(n));
ts.assign(9, Fenwick(n));
for (int i = 0; i < n; i++)
{
if (a[i] == b[i]) continue;
o1[cmap[a[i]]].upd(i+1, 1);
o2[cmap[b[i]]].upd(i+1, 1);
ts[cmap[a[i]]*3+cmap[b[i]]].upd(i+1, 1);
}
}
int get_distance(int x, int y) {
int su = 0;
bool val = 1;
vector<int> occ(9, 0);
for (int i = 0; i < 9; i++)
{
occ[i] = ts[i].qry(x+1, y+1);
}
//sat 2 6 5 7
int sub = 0;
sub = min(occ[1], occ[3]);
su += sub;
occ[1] -= sub;
occ[3] -= sub;
sub = min(occ[2], occ[6]);
su += sub;
occ[2] -= sub;
occ[6] -= sub;
sub = min(occ[5], occ[7]);
su += sub;
occ[5] -= sub;
occ[7] -= sub;
for (int i = 0; i < 3; i++)
{
int out = 0;
int ing = 0;
for (int j = 0; j < 3; j++)
{
out += occ[i*3+j];
ing += occ[j*3+i];
}
if (out != ing) {
val = 0;
break;
}
}
if (!val) return -1;
int esu = -1;
for (int i = 0; i < 9; i++)
{
esu += occ[i];
}
if (esu > 0) {
su += esu;
}
return su;
}
