#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
int numswaps[3][3][maxn];
int n;
int fin(char a){
if(a=='A')
return 0;
if(a=='T')
return 1;
return 2;
}
void init(string a, string b) {
n=a.size();
for(int i = 0;i<3;i++){
for(int j = 0;j<3;j++){
fill(numswaps[i][j],numswaps[i][j]+n,0);
}
}
numswaps[fin(a[0])][fin(b[0])][0]=1;
for(int i = 1;i<n;i++){
for(int s = 0;s<3;s++){
for(int e = 0;e<3;e++){
numswaps[s][e][i]=numswaps[s][e][i-1];
}
}
numswaps[fin(a[i])][fin(b[i])][i]++;
}
}
int get_distance(int x, int y) {
int freq[3][3];
for(int i = 0;i<3;i++){
for(int j = 0;j<3;j++){
freq[i][j]=numswaps[i][j][y];
if(x){
freq[i][j]-=numswaps[i][j][x-1];
}
}
}
if((freq[0][1]+freq[0][2]!=freq[1][0]+freq[2][0])||(freq[1][0]+freq[1][2]!=freq[0][1]+freq[2][1])||(freq[2][0]+freq[2][1]!=freq[0][2]+freq[1][2])){
return -1;
}
//freqs are fine now.
//so possible
int ans = 0;
for(int i = 0;i<3;i++){
for(int j = 0;j<3;j++){
if(i==j)
continue;
int a = min(freq[i][j],freq[j][i]);
ans+=a;
freq[i][j]-=a;
freq[j][i]-=a;
}
}
multiset<int>lef;
for(int i = 0;i<3;i++){
for(int j = 0;j<3;j++){
if(i==j)
continue;
if(freq[i][j])
lef.insert(freq[i][j]);
}
}
if(lef.size()==0){
return ans;
}
assert(lef.size()==3);
ans+=(*lef.begin());
ans+=((*(--lef.end()))+(*(--(--lef.end()))))/2;
return ans;
}
