#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 69;
int a[N][3];
int b[N][3];
int p[N][3][3];
int n;
void init(string A, string B) {
n = A.length();
for (int i = 1; i <= n; i++){
if (A[i - 1] == 'A') a[i][0]++;
else if (A[i - 1] == 'T') a[i][1]++;
else a[i][2]++;
}
for (int i = 1; i <= n; i++){
if (B[i - 1] == 'A') b[i][0]++;
else if (B[i - 1] == 'T') b[i][1]++;
else b[i][2]++;
}
for (int i = 1; i <= n; i++){
int k1 = 0, k2 = 0;
for (int j = 0; j < 3; j++){
if (a[i][j] > 0) k1 = j;
if (b[i][j] > 0) k2 = j;
}
p[i][k1][k2]++;
}
for (int i = 1; i <= n; i++){
for (int j = 0; j < 3; j++){
a[i][j] += a[i - 1][j];
b[i][j] += b[i - 1][j];
for (int k = 0; k < 3; k++)
p[i][j][k] += p[i - 1][j][k];
}
}
}
int get_distance(int x, int y) {
x++;
y++;
int ans = 0;
for (int j = 0; j < 3; j++){
int v1 = a[y][j] - a[x - 1][j];
int v2 = b[y][j] - b[x - 1][j];
if (v1 != v2) return -1;
}
int change[3][3];
for (int j = 0; j < 3; j++){
for (int k = 0; k < 3; k++){
if (j != k)
change[j][k] = p[y][j][k] - p[x - 1][j][k];
else change[j][k] = 0;
}
}
for (int j = 0; j < 3; j++){
for (int k = j + 1; k < 3; k++){
int op = min(change[j][k], change[k][j]);
ans += op;
change[j][k] -= op;
change[k][j] -= op;
ans += change[j][k] + change[k][j];
}
}
int mx = -1;
for (int j = 0; j < 3; j++){
for (int k = 0; k < 3; k++){
mx = max(mx, change[j][k]);
}
}
ans -= mx;
return ans;
}
// int32_t main(){
// string a, b; cin >> a >> b;
// init(a, b);
// int q; cin >> q;
// while(q--){
// int x, y; cin >> x >> y;
// cout << get_distance(x, y) << "\n";
// }
// return 0;
// }
