#include "dna.h"
#include <bits/stdc++.h>
#define endl "\n"
#define ff first
#define ss second
#define pb push_back
#define all(v) v.begin(), v.end()
using namespace std;
struct wavelet{
int mn, mx, nxt=1;
vector <vector <int>> t, pr;
vector <int> L, R;
void init(int mi, int ma) {
mn = mi, mx = ma;
t.pb({});
pr.pb({});
L.pb(-1);
R.pb(-1);
}
void build(int v, int tl, int tr, vector <int> &a) {
int tm = (tl + tr) / 2;
if (v == 1) {
t.pb({});
for (int i = 0; i < a.size(); i++) t[v].pb(a[i]);
}
while (pr.size() <= v) pr.pb({});
pr[v].pb(0);
for (int i = 0; i < t[v].size(); i++) {
if (t[v][i] <= tm) pr[v].pb(1);
else pr[v].pb(0);
}
for (int i = 1; i < pr[v].size(); i++) pr[v][i] += pr[v][i-1];
if (tl == tr) return;
while (L.size() <= v) L.pb(-1);
while (R.size() <= v) R.pb(-1);
L[v] = ++nxt;
R[v] = ++nxt;
while (t.size() <= R[v]) t.pb({});
for (int i = 0; i < t[v].size(); i++) {
if (t[v][i] <= tm) t[L[v]].pb(t[v][i]);
else t[R[v]].pb(t[v][i]);
}
if (t[L[v]].size()) build(L[v], tl, tm, a);
if (t[R[v]].size()) build(R[v], tm+1, tr, a);
}
void bld(vector <int> &v) { build(1, mn, mx, v); }
int findk(int v, int tl, int tr, int l, int r, int k) {
if (tl == tr) return tl;
int tm = (tl + tr) / 2;
int ct = pr[v][r+1] - pr[v][l];
if (ct >= k) return findk(L[v], tl, tm, pr[v][l], pr[v][r+1] - 1, k);
else return findk(R[v], tm+1, tr, l - pr[v][l], r - pr[v][r+1], k - ct);
}
int kth(int l, int r, int k) { return findk(1, mn, mx, l, r, k); }
int findsmallerk(int v, int tl, int tr, int l, int r, int k) {
if (l > r) return 0;
if (tl == tr) return r - l + 1;
int tm = (tl + tr) / 2;
if (k <= tm) {
return findsmallerk(L[v], tl, tm, pr[v][l], pr[v][r+1] - 1, k);
}
else {
return findsmallerk(R[v], tm+1, tr, l - pr[v][l], r - pr[v][r+1], k) + pr[v][r+1] - pr[v][l];
}
}
int smallk(int l, int r, int k) { return findsmallerk(1, mn, mx, l, r, k); }
int findbiggerk(int v, int tl, int tr, int l, int r, int k) {
if (l > r) return 0;
if (tl == tr) return r - l + 1;
int tm = (tl + tr) / 2;
if (k <= tm) {
return findbiggerk(L[v], tl, tm, pr[v][l], pr[v][r+1] - 1, k) + r - l + 1 - pr[v][r+1] + pr[v][l];
}
else {
return findbiggerk(R[v], tm+1, tr, l - pr[v][l], r - pr[v][r+1], k);
}
}
int bigk(int l, int r, int k) { return findbiggerk(1, mn, mx, l, r, k); }
};
vector <int> pr1[3], pr2[3], is;
wavelet t;
vector <int> l;
void init(string a, string b) {
int n = a.size();
for (int i = 0; i < 3; i++) {
pr1[i].assign(n, 0);
pr2[i].assign(n, 0);
}
is.assign(n, 0);
for (int i = 0; i < n; i++) {
if (a[i] == 'A') pr1[0][i]++;
else if (a[i] == 'T') pr1[1][i]++;
else pr1[2][i]++;
if (b[i] == 'A') pr2[0][i]++;
else if (b[i] == 'T') pr2[1][i]++;
else pr2[2][i]++;
}
for (int i = 0; i < n; i++) {
if (a[i] != b[i]) is[i]++;
}
map <pair<char, char>, vector <int>> m;
vector <pair<int, int>> rn;
for (int i = 0; i < n; i++) {
if (a[i] == b[i]) continue;
if (m[{b[i], a[i]}].size()) {
rn.pb({m[{b[i], a[i]}].back(), i});
m[{b[i], a[i]}].pop_back();
}
else m[{a[i], b[i]}].pb(i);
}
sort(all(rn));
vector <int> r;
for (auto &i : rn) {
l.pb(i.ff);
r.pb(i.ss);
}
t.init(0, n);
t.bld(r);
}
int get_distance(int x, int y) {
for (int i = 0; i < 3; i++) {
int a = pr1[i][y] - (x == 0 ? 0 : pr1[i][x-1]);
int b = pr2[i][y] - (x == 0 ? 0 : pr2[i][x-1]);
if (a != b) return -1;
}
int res = is[y] - (x == 0 ? 0 : is[x-1]);
int id = lower_bound(all(l), x) - l.begin();
return res - t.smallk(id, l.size()-1, y);
}
