#include "dna.h"
#include <algorithm>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
//#define int long long
#define loop(X, N) for(int X = 0; X < (N); X++)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
int n;
vi a, b;
//vi prefixA[3], prefixB[3];
vi prefix[9];
void init(string A, string B) {
n = (int)A.size();
a = vi(n);
b = vi(n);
loop(i, n) {
if (A[i] == 'A') a[i] = 0;
if (A[i] == 'T') a[i] = 1;
if (A[i] == 'C') a[i] = 2;
if (B[i] == 'A') b[i] = 0;
if (B[i] == 'T') b[i] = 1;
if (B[i] == 'C') b[i] = 2;
}
loop(j, 9) prefix[j] = vi(n + 1);
for (int i = 1; i <= n; i++) {
loop(j, 9) {
prefix[j][i] = prefix[j][i - 1];
}
prefix[a[i - 1] * 3 + b[i - 1]][i]++;
}
// loop(i, 3) {
// prefixA[i] = vi(n + 1);
// prefixB[i] = vi(n + 1);
// for (int j = 1; j <= n; j++) {
// prefixA[i][j] = prefixA[i][j - 1] + (a[j - 1] == i);
// prefixB[i][j] = prefixB[i][j - 1] + (b[j - 1] == i);
// }
// }
}
int get_distance(int x, int y) {
// loop(i, 3) {
// if (prefixA[i][y + 1] - prefixA[i][x] != prefixB[i][y + 1] - prefixB[i][x])
// return -1;
// }
int letterCounts[3] = { 0 };
int counts[3][3] = { 0 };
loop(j, 9) {
counts[j / 3][j % 3] = prefix[j][y + 1] - prefix[j][x];
}
letterCounts[0] = counts[0][1] + counts[0][2] - counts[1][0] - counts[2][0];
letterCounts[1] = counts[1][2] + counts[1][0] - counts[2][1] - counts[0][1];
letterCounts[2] = counts[2][0] + counts[2][1] - counts[0][2] - counts[1][2];
if (letterCounts[0] != 0 || letterCounts[1] != 0 || letterCounts[2] != 0)
return -1;
int swap1 = min(counts[1][0], counts[0][1]);
counts[1][0] -= swap1;
counts[0][1] -= swap1;
int swap2 = min(counts[2][0], counts[0][2]);
counts[2][0] -= swap2;
counts[0][2] -= swap2;
int swap3 = min(counts[2][1], counts[1][2]);
counts[2][1] -= swap3;
counts[1][2] -= swap3;
int result = swap1 + swap2 + swap3;
int left = (y - x + 1) - 2 * (swap1 + swap2 + swap3) - counts[0][0] - counts[1][1] - counts[2][2];
result += left / 3 * 2;
return result;
}
