#include <bits/stdc++.h>
#include "dna.h"
using namespace std;
int n;
vector<int> a, b;
vector<vector<int>> p1, p2, cnt;
void init(string A, string B) {
n = A.size();
a.resize(n);
b.resize(n);
for (int i = 0; i < n; i++) {
if (A[i] == 'A') {
a[i] = 0;
} else if (A[i] == 'T') {
a[i] = 1;
} else {
a[i] = 2;
}
if (B[i] == 'A') {
b[i] = 0;
} else if (B[i] == 'T') {
b[i] = 1;
} else {
b[i] = 2;
}
}
p1.resize(3, vector<int>(n + 1));
p2.resize(3, vector<int>(n + 1));
for (int i = 0; i < 3; i++) {
for (int j = 0; j < n; j++) {
p1[i][j + 1] = p1[i][j] + (a[j] == i);
p2[i][j + 1] = p2[i][j] + (b[j] == i);
}
}
cnt.resize(9, vector<int>(n + 1));
for (int i = 0; i < 9; i++) {
for (int j = 0; j < n; j++) {
cnt[i][j + 1] = cnt[i][j] + (a[j] * 3 + b[j] == i);
}
}
}
int get_distance(int l, int r) {
auto get = [&](vector<int> &p) {
return p[r + 1] - p[l];
};
for (int i = 0; i < 3; i++) {
if (get(p1[i]) != get(p2[i])) {
return -1;
}
}
int one = get(cnt[0]) + get(cnt[4]) + get(cnt[8]);
int two = min(get(cnt[1]), get(cnt[3])) + min(get(cnt[2]), get(cnt[6])) + min(get(cnt[5]), get(cnt[7]));
int ans = one + two + ((r - l + 1) - one - two * 2) / 3 * 2;
return ans;
}
