#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
template <typename T>
struct fenwick_tree
{
vector<T> t;
fenwick_tree() {}
fenwick_tree(size_t n) { t.resize(n); }
void update(int64_t i, T x)
{
++i;
while (i <= t.size())
t[i - 1] += x, i += i & -i;
}
T range_sum(int64_t i, int64_t j)
{
T x = 0;
++j;
while (j)
x += t[j - 1], j -= j & -j;
while (i)
x -= t[i - 1], i -= i & -i;
return x;
}
};
constexpr size_t N = 100000;
string a, b;
fenwick_tree<int> at[3], bt[3];
bitset<N> matched;
void init(string a_, string b_)
{
a = a_;
b = b_;
for (size_t i = 0; i < 3; ++i)
at[i] = fenwick_tree<int>(a.size()), bt[i] = fenwick_tree<int>(b.size());
for (size_t i = 0; i < a.size(); ++i)
{
if (a[i] == 'A')
at[0].update(i, 1);
else if (a[i] == 'C')
at[1].update(i, 1);
else
at[2].update(i, 1);
if (b[i] == 'A')
bt[0].update(i, 1);
else if (b[i] == 'C')
bt[1].update(i, 1);
else
bt[2].update(i, 1);
}
}
bool equal_set_in_range(size_t i, size_t j)
{
return at[0].range_sum(i, j) == bt[0].range_sum(i, j) &&
at[1].range_sum(i, j) == bt[1].range_sum(i, j) &&
at[2].range_sum(i, j) == bt[2].range_sum(i, j);
}
int get_distance(int x, int y)
{
if (!equal_set_in_range(x, y))
return -1;
int ans = 0, num_matched = 0;
for (int i = x; i <= y; ++i)
if (a[i] == b[i])
matched[i] = 1, num_matched++;
for (int i = x; i <= y; ++i)
{
if (!matched[i])
{
for (int j = i + 1; j <= y; ++j)
{
if (a[i] == b[j] && a[j] == b[i])
{
num_matched += 2;
ans++;
matched[i] = 1;
matched[j] = 1;
break;
}
}
}
}
for (int i = x; i <= y; ++i)
matched[i] = 0;
return ans + ((y - x + 1 - num_matched) / 3) * 2;
}
