#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int pref[ N ][ 3 ][ 3 ];
map<char, int> mp = {
{'A', 0},
{'C', 1},
{'T', 2}
};
void init(string a, string b) {
int n = (int)a.size();
for(int i = 0;i < n;i++) {
for(int j = 0;j < 3;j++) {
for(int k = 0;k < 3;k++) {
if(i) pref[ i ][ j ][ k ] = pref[i - 1][ j ][ k ];
if(mp[a[i]] == j && mp[b[i]] == k) pref[i][j][k]++;
}
}
}
}
int get_distance(int l, int r) {
int w[3][3] = {};
int s1[ 3 ] = {}, s2[ 3 ] = {};
for(int i = 0;i < 3;i++) {
for(int j = 0;j < 3;j++) {
w[ i ][ j ] = pref[ r ][ i ][ j ];
if(l) w[ i ][ j ] -= pref[l - 1][ i ][ j ];
s1[ i ] += w[ i ][ j ];
s2[ j ] += w[ i ][ j ];
// cout << w[ i ][ j ] << ' ';
}
// cout << '\n';
}
for(int i = 0;i < 3;i++)
if(s1[ i ] != s2[ i ]) return -1;
int res = 0;
for(int i = 0;i < 3;i++) {
for(int j = 0;j < 3;j++) {
if(i == j) continue;
int c = min(w[ i ][ j ], w[ j ][ i ]);
res += c;
w[ i ][ j ] -= c;
w[ j ][ i ] -= c;
w[ i ][ i ] += c;
w[ j ][ j ] += c;
}
}
return res + 2 * max(w[ 0 ][ 1 ], w[ 0 ][ 2 ]);
}
// int main() {
// int n, q;
// cin >> n >> q;
// string a, b;
// cin >> a >> b;
// init(a, b);
// while(q--) {
// int x, y;
// cin >> x >> y;
// cout << get_distance(x, y) << '\n';
// }
// }
