#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
int get_id(char c) { return c == 'A' ? 0 : c == 'C' ? 1 : 2; }
int n;
vi A, B;
vector<array<int, 9> > Fr;
void init(string a, string b) {
n = a.size();
for(auto it : a) A.push_back(get_id(it));
for(auto it : b) B.push_back(get_id(it));
Fr.resize(n);
for(int i = 0; i < n; ++i) {
for(int j = 0; j < 9; ++j)
Fr[i][j] = i ? Fr[i - 1][j] : 0;
++Fr[i][A[i] * 3 + B[i]];
}
}
int get_distance(int x, int y) {
array<array<int, 3>, 3> Nr;
for(int i = 0; i < 3; ++i)
for(int j = 0; j < 3; ++j) Nr[i][j] = 0;
for(int i = 0; i < 9; ++i) {
int delta = Fr[y][i];
if(x) delta -= Fr[x - 1][i];
Nr[i / 3][i % 3] = delta;
}
// for(int i = 0; i < 3; ++i) {
// for(int j = 0; j < 3; ++j) {
// cout << Nr[i][j] << " ";
// }
// cout << "\n";
// }
// cout << "\n";
array<int, 3> delta;
for(int i = 0; i < 3; ++i) delta[i] = 0;
for(int i = 0; i < 3; ++i)
for(int j = 0; j < 3; ++j) {
if(i != j) {
delta[i] -= Nr[i][j];
delta[j] += Nr[i][j];
}
}
for(int i = 0; i < 3; ++i)
if(delta[i]) return -1;
int re = 0;
for(int i = 0; i < 3; ++i)
for(int j = i + 1; j < 3; ++j) {
if(Nr[i][j] && Nr[j][i]) {
int v = min(Nr[i][j], Nr[j][i]);
Nr[i][j] -= v; Nr[j][i] -= v;
re += v;
}
}
// for(int i = 0; i < 3; ++i) {
// for(int j = 0; j < 3; ++j) {
// cout << Nr[i][j] << " ";
// }
// cout << "\n";
// }
// cout << "\n";
vi P = {0, 1, 2};
do {
int v = n;
for(int i = 0; i < 3; ++i) {
int nxt = P[(i + 1) % 3];
v = min(v, Nr[P[i]][nxt]);
}
re += 2 * v;
for(int i = 0; i < 3; ++i) {
int nxt = P[(i + 1) % 3];
Nr[P[i]][nxt] -= v;
}
} while (next_permutation(P.begin(), P.end()));
// for(int i = 0; i < 3; ++i) {
// for(int j = 0; j < 3; ++j) {
// cout << Nr[i][j] << " ";
// }
// cout << "\n";
// }
// cout << "\n";
return re;
}
