#include "dna.h"
#include<bits/stdc++.h>
using namespace std ;
#define maxn 200009
#define ll long long
#define pb push_back
#define fi first
#define se second
#define left id<<1
#define right id<<1|1
#define re exit(0);
#define _lower(x) lower_bound(v.begin(),v.end(),x)-v.begin()+1
#define TIME ( 1.0*clock() / CLOCKS_PER_SEC )
const int mod = 1e9+7 ;
const int INF = 1e9 ;
typedef vector<int> vi ;
typedef pair<int,int> pii ;
typedef vector<pii> vii ;
template < typename T > void chkmin ( T &a , T b ) { if ( a > b ) a = b ; }
template < typename T > void chkmax ( T &a , T b ) { if ( a < b ) a = b ; }
void add ( int &a , int b )
{
a += b ;
if ( a >= mod ) a -= mod ;
if ( a < 0 ) a += mod ;
}
int n , sum [maxn][3][3] , ch [maxn] ;
void init( string a , string b ) {
n = a.size() ;
ch ['A'] = 0 , ch ['C'] = 1 , ch ['T'] = 2 ;
for ( int i = 1 ; i <= n ; i ++ )
{
for ( int t1 = 0 ; t1 <= 2 ; t1 ++ )
{
for ( int t2 = 0 ; t2 <= 2 ; t2 ++ )
{
sum [i][t1][t2] = sum [i-1][t1][t2] ;
}
}
sum [i][ch[a[i-1]]][ch[b[i-1]]] ++ ;
}
}
int get_distance(int x, int y) {
int l = x+1 , r = y+1 ;
int temp [3][3] = {0} ;
for ( int t1 = 0 ; t1 <= 2 ; t1 ++ ) for ( int t2 = 0 ; t2 <= 2 ; t2 ++ ) temp [t1][t2] = sum [r][t1][t2] - sum [l-1][t1][t2] ;
int res = 0 ;
for ( int t1 = 0 ; t1 <= 2 ; t1 ++ ) for ( int t2 = 0 ; t2 <= 2 ; t2 ++ )
{
if ( t1 == t2 ) temp [t1][t2] = 0 ;
else
{
int c = min (temp[t1][t2],temp[t2][t1]) ;
temp [t1][t2] -= c , temp [t2][t1] -= c ;
res += c ;
}
}
for ( int t1 = 0 ; t1 <= 2 ; t1 ++ ) for ( int t2 = 0 ; t2 <= 2 ; t2 ++ )
{
if ( t1 == t2 ) continue ;
int k = 3^t1^t2 ;
int c = min({temp[t1][t2],temp[t2][k],temp[k][t1]}) ;
temp [t1][t2] -= c , temp [t2][k] -= c , temp [k][t1] -= c ;
res += c*2 ;
}
for ( int t1 = 0 ; t1 <= 2 ; t1 ++ ) for ( int t2 = 0 ; t2 <= 2 ; t2 ++ ) if ( temp [t1][t2] ) return - 1 ;
return res;
}
