#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define ALL(v) v.begin(), v.end()
#define pb push_back
#define SZ(a) ((int)a.size())
int num[256];
int prea[3][100005], preb[3][100005];
int atdiff[100005], ac[100005], tc[100005], ca[100005], ct[100005];
int get_sum(int *arr, int l, int r) {
if (l == 0)
return arr[r];
return arr[r] - arr[l - 1];
}
void init(string a, string b) {
int n = SZ(a);
num['A'] = 0, num['T'] = 1, num['C'] = 2;
for (int i = 0; i < n; ++i) {
++prea[num[int(a[i])]][i];
++preb[num[int(b[i])]][i];
atdiff[i] = (a[i] != b[i] && a[i] != 'C' && b[i] != 'C');
ac[i] = (a[i] == 'A' && b[i] == 'C');
tc[i] = (a[i] == 'T' && b[i] == 'C');
ca[i] = (a[i] == 'C' && b[i] == 'A');
ct[i] = (a[i] == 'C' && b[i] == 'T');
}
for (int i = 1; i < n; ++i) {
prea[0][i] += prea[0][i - 1];
prea[1][i] += prea[1][i - 1];
prea[2][i] += prea[2][i - 1];
preb[0][i] += preb[0][i - 1];
preb[1][i] += preb[1][i - 1];
preb[2][i] += preb[2][i - 1];
atdiff[i] += atdiff[i - 1];
ac[i] += ac[i - 1];
tc[i] += tc[i - 1];
ca[i] += ca[i - 1];
ct[i] += ct[i - 1];
}
}
int get_distance(int x, int y) {
if (get_sum(prea[0], x, y) != get_sum(preb[0], x, y)) {
return -1;
}
if (get_sum(prea[1], x, y) != get_sum(preb[1], x, y)) {
return -1;
}
if (get_sum(prea[2], x, y) != get_sum(preb[2], x, y)) {
return -1;
}
int cd = get_sum(ac, x, y) + get_sum(tc, x, y);
int once = min(get_sum(ac, x, y), get_sum(ca, x, y)) + min(get_sum(tc, x, y), get_sum(ct, x, y));
return cd + (cd - once + get_sum(atdiff, x, y)) / 2;
}
