#include "dna.h"
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
ll p = 1;
vector<vector<vector<ll>>> seg(3, vector<vector<ll>>(3, vector<ll>(500000)));
vector<vector<ll>> pref_a(3, vector<ll>(100100)), pref_b(3, vector<ll>(100100));
ll sum(ll a, ll b, vector<ll> &v){
a += p, b += p;
ll s = 0;
while(a <= b){
if(a % 2 == 1) s += v[a++];
if(b % 2 == 0) s += v[b--];
a /= 2; b /= 2;
}
return s;
}
void init(string A, string B) {
ll n = A.size();
while(p <= n) p *= 2;
vector<ll> a(n), b(n);
for(ll i = 0; i < n; i++){
if(A[i] == 'A') a[i] = 0;
if(A[i] == 'T') a[i] = 1;
if(A[i] == 'C') a[i] = 2;
if(B[i] == 'A') b[i] = 0;
if(B[i] == 'T') b[i] = 1;
if(B[i] == 'C') b[i] = 2;
pref_a[0][i+1] = pref_a[0][i] + (a[i] == 0), pref_a[1][i+1] = pref_a[1][i] + (a[i] == 1), pref_a[2][i+1] = pref_a[2][i] + (a[i] == 2);
pref_b[0][i+1] = pref_b[0][i] + (b[i] == 0), pref_b[1][i+1] = pref_b[1][i] + (b[i] == 1), pref_b[2][i+1] = pref_b[2][i] + (b[i] == 2);
seg[a[i]][b[i]][i+p] = 1;
}
for(ll k = 0; k <= 2; k++) for(ll l = 0; l <= 2; l++){
for(ll i = p-1; i > 0; i--) seg[k][l][i] = seg[k][l][2*i] + seg[k][l][2*i+1];
}
}
int get_distance(int x, int y) {
vector<vector<ll>> cnt(3, vector<ll>(3));
for(ll i = 0; i <= 2; i++) if(pref_a[i][y+1] - pref_a[i][x] != pref_b[i][y+1] - pref_b[i][x]) return -1;
for(ll i = 0; i <= 2; i++) for(ll j = 0; j <= 2; j++) cnt[i][j] = sum(x, y, seg[i][j]);
return min(cnt[0][1], cnt[1][0]) + min(cnt[0][2], cnt[2][0]) + min(cnt[1][2], cnt[2][1]) +
(max(cnt[0][1], cnt[1][0]) - min(cnt[0][1], cnt[1][0])) * 2;
}
