#include "dna.h"
//ᴇᴀᴄʜ ᴘᴇʀꜱᴏɴ ᴡɪʟʟ ᴏɴʟʏ ʜᴀᴠᴇ ᴡʜᴀᴛ ᴛʜᴇʏ ᴇɴᴅᴇᴀᴠᴏᴜʀᴇᴅ ᴛᴏᴡᴀʀᴅꜱ [53:39]
//Author: Sazid Hasan
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double dl;
typedef vector<int> vi;
typedef vector<vector<int>> vii;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*(b/gcd(a,b)))
#define spc " "
#ifdef ONLINE_JUDGE
#define debarr(array)
#define deb(x)
#define del
#else
#define debarr(array) for(int w = 0; w < array.size(); w++) cerr << #array << "-" << w << " = " << array[w] << endl;
#define deb(x) cerr << #x << " = " << x << endl;
#define del cerr << '\n';
#endif
const double PI = acos(-1);
const int MOD = 1000000007;
const int inf = (2147483647);
vector<vii> pref;
void init(std::string a, std::string b) {
int n = a.size();
for(auto &x: a){
if(x=='A') x = 0;
if(x=='T') x = 1;
if(x=='C') x = 2;
}
for(auto &x: b){
if(x=='A') x = 0;
if(x=='T') x = 1;
if(x=='C') x = 2;
}
pref.resize(n, vii(3, vi(3, 0)));
pref[0][a[0]][b[0]]++;
for(int i = 1; i < n; i++){
pref[i] = pref[i-1];
pref[i][a[i]][b[i]]++;
}
}
int inRange(int l, int r, int a, int b){
return pref[r][a][b] - (l>0 ? pref[l-1][a][b] : 0);
}
bool valid(int x, int y){
int a, b;
a = inRange(x, y, 0, 1)+inRange(x, y, 0, 2);
b = inRange(x, y, 2, 0)+inRange(x, y, 1, 0);
if(a!=b) return 0;
a = inRange(x, y, 1, 0)+inRange(x, y, 1, 2);
b = inRange(x, y, 2, 1)+inRange(x, y, 0, 1);
if(a!=b) return 0;
a = inRange(x, y, 2, 1)+inRange(x, y, 2, 0);
b = inRange(x, y, 0, 2)+inRange(x, y, 1, 2);
if(a!=b) return 0;
return 1;
}
int get_distance(int x, int y) {
if(!valid(x, y)) return -1;
int ans = inRange(x, y, 0, 1) + inRange(x, y, 0, 2);
ans += max(inRange(x, y, 1, 2), inRange(x, y, 2, 1));
return ans;
return 0;
}
