#include<bits/stdc++.h>
#include "dna.h"
using namespace std;
int minSwaps(array<array<int, 3>, 3> a){
int res = 0;
int x = min(a[0][1], a[1][0]);
res += x;
a[0][1] -= x;
a[1][0] -= x;
x = min(a[0][2], a[2][0]);
res += x;
a[0][2] -= x;
a[2][0] -= x;
x = min(a[1][2], a[2][1]);
res += x;
a[1][2] -= x;
a[2][1] -= x;
if(a[0][1] + a[0][2] != a[1][0] + a[2][0] || a[1][0] + a[1][2] != a[0][1] + a[0][2] || a[2][0] + a[2][1] != a[0][2] + a[1][2])return -1;
res += 2 * (a[0][1] + a[0][2] + a[1][0] + a[1][2] + a[2][0] + a[2][1])/3;
return res;
}
class Tree{
private:
int lrSize = 2;
vector<array<array<int, 3>, 3>> v;
void update(int pos){
for(int i = 0; i < 3; i++){
for(int j = 0; j < 3; j++){
v[pos][i][j] = v[2*pos][i][j] + v[2*pos + 1][i][j];
}
}
}
void rangeSum(int a, int b, int l, int r, int pos, array<array<int,3>, 3>& ans){
if(b < l || r < a)return;
if(a <= l && r <= b){
for(int i = 0; i < 3; i++){
for(int j = 0; j < 3; j++)ans[i][j] += v[pos][i][j];
}
}else{
int m = (l + r)/2;
rangeSum(a, b, l, m, 2*pos, ans);
rangeSum(a, b, m+1, r, 2*pos+1, ans);
}
}
public:
void init(string a, string b){
int n = a.length();
while(lrSize < n)lrSize *= 2;
v.resize(2*lrSize);
for(int i = 0; i < lrSize; i++){
for(int j = 0; j < 3; j++){
for(int k = 0; k < 3; k++){
v[lrSize + i][j][k] = 0;
}
}
int x, y;
if(a[i] == 'A') x = 0;
else if(a[i] == 'T')x=1;
else x = 2;
if(b[i] == 'A') y = 0;
else if(b[i] == 'T')y=1;
else y = 2;
if(i < n){
v[lrSize+i][x][y] = 1;
}
}
for(int i = lrSize - 1; i >= 1; i--)update(i);
}
Tree(){
}
int getAns(int a, int b){
array<array<int, 3>, 3> ans;
for(int i = 0; i < 3; i++){
for(int j = 0; j < 3; j++)ans[i][j] = 0;
}
rangeSum(a, b, 0, lrSize-1, 1, ans);
return minSwaps(ans);
}
};
Tree tree;
void init(string a, string b){
tree.init(a, b);
}
int get_distance(int x, int y){
return tree.getAns(x, y);
}
/*
int main(){
int n, q; cin>>n>>q;
string a, b; cin>>a>>b;
init(a, b);
for(int i = 0; i < q; i++){
int x, y; cin>>x>>y;
cout<<get_distance(x, y)<<"\n";
}
}*/
