#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
// 0 = ac, 1 = at, 2 = ca, 3 = ct, 4 = ta, 5 = tc
// (0 3 4), (1 5 2)
// (0 2), (1 4), (3 5)
int qs[6][N];
void init(std::string a, std::string b) {
int n = a.size();
a = '.'+a;
b = '.'+b;
for(int i = 1; i <= n; ++i){
qs[0][i] = qs[0][i-1];
qs[1][i] = qs[1][i-1];
qs[2][i] = qs[2][i-1];
qs[3][i] = qs[3][i-1];
qs[4][i] = qs[4][i-1];
qs[5][i] = qs[5][i-1];
if(a[i] == 'A'){
if(b[i] == 'C') qs[0][i]++;
else if(b[i] == 'T') qs[1][i]++;
}else if(a[i] == 'C'){
if(b[i] == 'A') qs[2][i]++;
else if(b[i] == 'T') qs[3][i]++;
}else if(a[i] == 'T'){
if(b[i] == 'A') qs[4][i]++;
else if(b[i] == 'C') qs[5][i]++;
}
}
}
int get_distance(int l, int r) {
l++, r++;
int res = 0;
int cnt[6];
for(int i = 0; i < 6; ++i) cnt[i] = qs[i][r]-qs[i][l-1];
while(1){
if(cnt[0] && cnt[2]){
int mn = min(cnt[0], cnt[2]);
res += mn;
cnt[0] -= mn;
cnt[2] -= mn;
}else if(cnt[1] && cnt[4]){
int mn = min(cnt[1], cnt[4]);
res += mn;
cnt[1] -= mn;
cnt[4] -= mn;
}else if(cnt[3] && cnt[5]){
int mn = min(cnt[3], cnt[5]);
res += mn;
cnt[3] -= mn;
cnt[5] -= mn;
}else if(cnt[0] && cnt[3] && cnt[4]){
int mn = min({cnt[0], cnt[3], cnt[4]});
res += 2*mn;
cnt[0] -= mn;
cnt[3] -= mn;
cnt[4] -= mn;
}else if(cnt[2] && cnt[5] && cnt[1]){
int mn = min({cnt[2], cnt[5], cnt[1]});
res += 2*mn;
cnt[2] -= mn;
cnt[5] -= mn;
cnt[1] -= mn;
}else{
bool chk = 1;
for(int i = 0; i < 6; ++i) if(cnt[i]) chk = 0;
if(chk) return res;
else break;
}
}
return -1;
}
