#include "dna.h"
#include <vector>
#include <algorithm>
using namespace std;
string A, B;
int n;
vector<int> pref1, pref2, pref3, pref4, pref5, pref6;
void init(std::string a, std::string b) {
A = a, B = b;
n = (int)A.size();
pref1 = pref2 = pref3 = pref4 = pref5 = pref6 = vector<int>(n+1, 0);
for(int i=0; i<n; i++) {
if(A[i] == B[i]) {
pref1[i+1] += pref1[i];
pref2[i+1] += pref2[i];
pref3[i+1] += pref3[i];
pref4[i+1] += pref4[i];
pref5[i+1] += pref5[i];
pref6[i+1] += pref6[i];
continue;
}
if(A[i] == 'A') {
if(B[i] == 'T') pref1[i+1]++;
else if(B[i] == 'C') pref2[i+1]++;
}
else if(A[i] == 'T') {
if(B[i] == 'A') pref3[i+1]++;
else if(B[i] == 'C') pref4[i+1]++;
}
else {
if(B[i] == 'A') pref5[i+1]++;
else if(B[i] == 'T') pref6[i+1]++;
}
pref1[i+1] += pref1[i];
pref2[i+1] += pref2[i];
pref3[i+1] += pref3[i];
pref4[i+1] += pref4[i];
pref5[i+1] += pref5[i];
pref6[i+1] += pref6[i];
}
}
int get_distance(int x, int y) {
int msk=1, ret=0, aux=-1;
int p1 = pref1[y+1] - pref1[x],
p2 = pref2[y+1] - pref2[x],
p3 = pref3[y+1] - pref3[x],
p4 = pref4[y+1] - pref4[x],
p5 = pref5[y+1] - pref5[x],
p6 = pref6[y+1] - pref6[x];
msk &= (p1 + p2 == p3 + p5);
ret += p1 + p2;
aux = min(p1, p3); p3 -= aux;
aux = min(p2, p5); p5 -= aux;
p4 += p3, p6 += p5;
p1 = p2 = p3 = p5 = 0;
msk &= (p3 + p4 == p1 + p6);
ret += p3 + p4;
aux = min(p1, p3); p1 -= aux;
aux = min(p4, p6); p6 -= aux;
p2 += p1, p5 += p6;
p3 = p4 = p1 = p6 = 0;
msk &= (p5 + p6 == p2 + p4);
ret += p5 + p6;
aux = min(p5, p2); p2 -= aux;
aux = min(p6, p4); p4 -= aux;
p1 += p2, p3 += p4;
p5 = p6 = p2 = p4 = 0;
return (msk)? ret : -1;
}
