#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 4e5 + 10;
struct Node{
vector<int> cont;
vector<vector<int>> pares;
Node( int a = 3, int b = 3 ){
cont.resize(3);
pares.resize(3, vector<int>(3));
if( a < 3 && b < 3 ){
cont[a]++; cont[b]--;
pares[a][b]++;
}
}
Node operator + ( Node n ){
Node resp;
for( int i = 0; i < 3; i++ ){
resp.cont[i] = cont[i] + n.cont[i];
for( int j = 0; j < 3; j++ ) resp.pares[i][j] = pares[i][j] + n.pares[i][j];
}
return resp;
}
} seg[4*maxn];
int id( char c ){
if( c == 'A' ) return 0;
if( c == 'T' ) return 1;
return 2;
}
void build( int pos, int ini, int fim, string &a, string &b ){
if( ini == fim ){ seg[pos] = Node( id(a[ini]), id(b[ini]) ); return; }
int l = 2*pos, r = 2*pos + 1, mid = ( ini + fim )/2;
build( l, ini, mid, a, b ); build( r, mid + 1, fim, a, b );
seg[pos] = seg[l] + seg[r];
}
Node query( int pos, int ini, int fim, int ki, int kf ){
if( ki > fim || ini > kf ) return seg[0];
if( ki <= ini && fim <= kf ) return seg[pos];
int l = 2*pos, r = 2*pos + 1, mid = ( ini + fim )/2;
return query( l, ini, mid, ki, kf ) + query( r, mid + 1, fim, ki, kf );
}
int n;
void init( string a, string b ){
n = a.size();
build( 1, 0, n - 1, a, b );
}
int get_distance(int l, int r) {
Node resp = query( 1, 0, n - 1, l, r );
bool ok = true;
for( int i = 0; i < 3; i++ ) if( resp.cont[i] != 0 ) ok = false;
if( !ok ) return -1;
int tot = 0;
for( int i = 0; i < 3; i++ ){
resp.pares[i][i] = 0;
for( int j = i + 1; j < 3; j++ ){
int aux = min( resp.pares[i][j], resp.pares[j][i] );
resp.pares[i][j] -= aux; resp.pares[j][i] -= aux;
tot += aux;
}
}
int qtd = 0;
for( int i = 0; i < 3; i++ ) for( int j = 0; j < 3; j++ ) qtd = max( qtd, resp.pares[i][j] );
tot += 2*qtd;
return tot;
}
