#include <iostream>
#include <vector>
#include "dna.h"
using namespace std;
string a;
string b;
vector<int> dp[3][3];
int curr[3][3];
void init(string a1, string b1){
a = a1;
b = b1;
int n = a.size();
for(int i = 0; i<n; i++){
if(a[i] == 'T') a[i] = '0';
else if(a[i] == 'C') a[i] = '1';
else if(a[i] == 'A') a[i] = '2';
if(b[i] == 'T') b[i] = '0';
else if(b[i] == 'C') b[i] = '1';
else if(b[i] == 'A') b[i] = '2';
}
for(int i = 0; i<3; i++){
for(int j = 0; j<3; j++) dp[i][j].assign(n, 0);
}
for(int i = 0; i<n; i++){
for(int ai = 0; ai<3; ai++){
for(int bi = 0; bi<3; bi++){
dp[ai][bi][i] = (i>0?dp[ai][bi][i-1]:0) + (a[i]-'0' == ai && b[i]-'0' == bi);
}
}
}
}
int get_distance(int l, int r){
for(int i = 0; i<3; i++){
for(int j = 0; j<3; j++){
curr[i][j] = dp[i][j][r] - (l>0?dp[i][j][l-1]:0);
}
}
int moves = 0;
for(int i = 0; i<3; i++){
for(int j = 0; j<3; j++){
if(i == j || curr[i][j] == 0) continue;
if(curr[j][i] >= curr[i][j]){
curr[j][i] -= curr[i][j];
moves += curr[i][j];
curr[i][j] = 0;
}
else{
moves += curr[j][i];
curr[i][j] -= curr[j][i];
curr[j][i] = 0;
int k = 0;
while(k==j || k==i) k++;
if(curr[k][i] < curr[i][j]) return -1;
curr[k][i] -= curr[i][j];
curr[k][j] += curr[i][j];
moves += curr[i][j];
curr[i][j] = 0;
}
}
}
return moves;
}
// int main(void){
// freopen("input.txt", "r", stdin);
// string a1, b1;
// int q;
// cin>>a1>>b1>>q;
// init(a1, b1);
// for(int i = 0; i<q; i++){
// int l, r; cin>>l>>r;
// cout<<get_distance(l, r)<<endl;
// }
// }
