#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> a , b , c , a_t , b_t , c_t;
vector<vector<int>> pref;
vector<char> q = {'A', 'T' , 'C'};
void init(string s , string t){
n = (int)s.length();
a.resize(n + 1); b.resize(n + 1); c.resize(n + 1); a_t.resize(n + 1); b_t.resize(n + 1); c_t.resize(n + 1); pref.resize(n + 1 , vector<int>(6));
for(int i = 0 ; i < n ; i++){
int cnt = 0;
for(int j = 0 ; j < (int)q.size() ; j++){
for(int m = 0 ; m < (int)q.size() ; m++){
char one = q[j] , two = q[m];
if(one == two) continue;
pref[i + 1][cnt] = pref[i][cnt] + (s[i] == one && t[i] == two);
cnt++;
}
}
}
for(int i = 0 ; i < n ; i++){
a[i + 1] = a[i] + (s[i] == 'A');
a_t[i + 1] = a_t[i] + (t[i] == 'A');
b[i + 1] = b[i] + (s[i] == 'T');
b_t[i + 1] = b_t[i] + (t[i] == 'T');
c[i + 1] = c[i] + (s[i] == 'C');
c_t[i + 1] = c_t[i] + (t[i] == 'C');
}
return ;
}
int get_distance(int x , int y){
if(a[y + 1] - a[x] == a_t[y + 1] - a_t[x] && b[y + 1] - b[x] == b_t[y + 1] - b_t[x] && c[y + 1] - c[x] == c_t[y + 1] - c_t[x]){
int AT = pref[y+1][0]-pref[x][0] , AC = pref[y+1][1]-pref[x][1] , TA = pref[y+1][2]-pref[x][2] , TC = pref[y+1][3] -pref[x][3] , CA = pref[y+1][4] - pref[x][4] , CT = pref[y+1][5] - pref[x][5];
int need_a = a[y + 1] - a[x] - (AT + AC);
int need_b = b[y + 1] - b[x] - (TA + TC);
int need_c = c[y + 1] - c[x] - (CA - CT);
int best_a = min(AT , TA) + min(AC , CA) , best_b = min(TA , AT) + min(TC , CT), best_c = min(CA , AC) + min(CT , TC) ;
int ans = best_a + best_b + best_c;
need_a -= best_a; need_b -= best_b; need_c -= best_c;
int p = (need_a + need_b + need_c) / 2 + 1;
return ans + p;
}
else return -1;
}
