#include "dna.h"
#define wiwihorz
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma loop-opt(on)
#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define rrep(i, a, b) for(int i = b; i >= a; i--)
#define all(x) x.begin(), x.end()
#define ceil(a, b) ((a + b - 1) / (b))
#define INF 1000000000000000000
#define MOD 1000000007
#define eps (1e-9)
using namespace std;
#define ll long long int
#define lld long double
#define pii pair<int, int>
#define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count())
#ifdef wiwihorz
#define print(a...) cerr << "Line " << __LINE__ << ": ", kout("[" + string(#a) + "] = ", a)
void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
void kout() {cerr << endl;}
template<class T1, class ... T2> void kout(T1 a, T2 ... e) { cerr << a << " ", kout(e...);}
#else
#define print(...) 0
#define vprint(...) 0
#endif
int n;
vector<int> cnta[3], cntb[3], p[3], rp[3];
char c[] = {'A', 'C', 'T'};
int to_int(char cc) {
rep(i, 0, 2) if(cc == c[i])
return i;
return -1;
}
void init(string a, string b) {
n = a.size();
rep(i, 0, 2) {
cnta[i].assign(n + 1, 0);
cntb[i].assign(n + 1, 0);
p[i].assign(n + 1, 0);
rp[i].assign(n + 1, 0);
}
rep(i, 1, n) {
int ca = to_int(a[i - 1]), cb = to_int(b[i - 1]);
cnta[ca][i] ++, cntb[cb][i] ++;
if(ca == cb);
else if(ca > cb) p[ca + cb - 1][i] ++;
else rp[ca + cb - 1][i] ++;
rep(j, 0, 2) {
cnta[j][i] += cnta[j][i - 1];
cntb[j][i] += cntb[j][i - 1];
p[j][i] += p[j][i - 1];
rp[j][i] += rp[j][i - 1];
}
}
return;
}
int get_distance(int x, int y) {
x++, y++;
rep(i, 0, 2) if(cnta[i][y] - cnta[i][x - 1]
!= cntb[i][y] - cntb[i][x - 1]) {
return -1;
}
int ans = 0, odd;
rep(i, 0, 2) {
int pos = p[i][y] - p[i][x - 1];
int neg = rp[i][y] - rp[i][x - 1];
odd = abs(pos - neg);
ans += min(pos, neg);
}
ans += odd * 2;
return ans;
}
