#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
namespace imple {
string a, b;
int n;
vector<int> diff;
vector<array<int, 3>> Ca, Cb;
const string DNA = "ATC";
void init(string _a, string _b) {
a = _a, b = _b;
diff.resize(a.size() + 1), Ca.resize(b.size() + 1), Cb.resize(b.size() + 1);
for (int i = 0; i < (int)a.size(); ++i) {
diff[i + 1] = diff[i] + (a[i] != b[i]);
}
for (int i = 0; i < (int)a.size(); ++i) {
Ca[i + 1] = Ca[i];
++Ca[i + 1][DNA.find(a[i])];
}
for (int i = 0; i < (int)b.size(); ++i) {
Cb[i + 1] = Cb[i];
++Cb[i + 1][DNA.find(b[i])];
}
}
int query(int l, int r) {
for (int i = 0; i < 3; ++i) {
if (Ca[r + 1][i] - Ca[l][i] != Cb[r + 1][i] - Cb[l][i]) {
return -1;
}
}
return (diff[r + 1] - diff[l] + 1) / 2;
}
}; // namespace imple
void init(string a, string b) { imple::init(a, b); }
int get_distance(int x, int y) { return imple::query(x, y); }
