#include "bits/stdc++.h"
#include "dna.h"
using namespace std;
const int maxn = 1e5 + 5;
int n, q;
string a, b;
int pref_a[maxn][3];
int pref_b[maxn][3];
int same[maxn];
void init(string a, string b) {
a = ' ' + a;
b = ' ' + b;
for(int i = 1; i <= n; ++i) {
if(a[i] == 'T') a[i] = 'B';
if(b[i] == 'T') b[i] = 'B';
}
for(int i = 1; i <= n; ++i) {
same[i] = same[i - 1] + (a[i] == b[i]);
for(int j = 0; j < 3; ++j) {
pref_a[i][j] = pref_a[i - 1][j];
pref_b[i][j] = pref_b[i - 1][j];
}
pref_a[i][a[i] - 'A']++;
pref_b[i][b[i] - 'A']++;
}
}
int get_distance(int x, int y) {
++x, ++y;
int res = 0;
for(int i = 0; i < 3; ++i) {
if(pref_a[y][i] - pref_a[x - 1][i] != pref_b[y][i] - pref_b[x - 1][i]) {
return -1;
}
}
res = same[y] - same[x - 1];
res = ((y - x + 1) - res + 1) / 2;
return res;
}
