#include <bits/stdc++.h>
#include "dna.h"
// author: aykhn
using namespace std;
typedef long long ll;
const int oo = INT_MAX;
const ll ooo = LONG_MAX;
const ll mod = 1e9 + 7;
#define OPT ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
#define pii pair<int,int>
#define pll pair<ll,ll>
#define all(v) v.begin(), v.end()
#define mpr make_pair
#define pb push_back
#define ts to_string
#define fi first
#define se second
#define inf 0x3F3F3F3F
#define ins insert
#define infll 0x3F3F3F3F3F3F3F3FLL
#define bpc __builtin_popcount
struct cus
{
int AC = 0;
int AT = 0;
int CA = 0;
int CT = 0;
int TA = 0;
int TC = 0;
};
int sz = 1;
vector<cus> tree;
string a, b;
cus MERGE(cus one, cus two)
{
cus res;
res.AT = one.AT + two.AT;
res.AC = one.AC + two.AC;
res.CA = one.CA + two.CA;
res.CT = one.CT + two.CT;
res.TA = one.TA + two.TA;
res.TC = one.TC + two.TC;
return res;
}
void build(int l, int r, int x)
{
if (l + 1 == r)
{
if (l < a.length() && a[l] != b[l])
{
if (a[l] == 'A' && b[l] == 'C') tree[x].AC++;
else if (a[l] == 'A' && b[l] == 'T') tree[x].AT++;
else if (a[l] == 'C' && b[l] == 'A') tree[x].CA++;
else if (a[l] == 'C' && b[l] == 'T') tree[x].CT++;
else if (a[l] == 'T' && b[l] == 'A') tree[x].TA++;
else if (a[l] == 'T' && b[l] == 'C') tree[x].TC++;
}
return;
}
int mid = (l + r) >> 1;
build(l, mid, 2*x+1);
build(mid, r, 2*x+2);
tree[x] = MERGE(tree[2*x+1], tree[2*x+2]);
}
cus get(int lx, int rx, int l, int r, int x)
{
if (l >= rx || r <= lx)
{
cus temp;
return temp;
}
if (l >= lx && r <= rx) return tree[x];
int mid = (l + r) >> 1;
return MERGE(get(lx, rx, l, mid, 2*x+1), get(lx, rx, mid, r, 2*x+2));
}
void init(string s1, string s2)
{
a = s1;
b = s2;
int n = s1.length();
while (sz < n) sz <<= 1;
cus temp;
temp.AC = temp.AT = temp.CA = temp.CT = temp.TA = temp.TC = 0;
tree.assign(sz * 2, temp);
build(0, sz, 0);
}
int get_distance(int l, int r)
{
cus x = get(l, r + 1, 0, sz, 0);
if (x.AT + x.AC != x.TA + x.CA || x.CA + x.CT != x.AC + x.TC || x.TA + x.TC != x.AT + x.CT) return -1;
//cout << "AC: " << x.AC << endl << "AT: " << x.AT << endl << "CA: " << x.CA << endl << "CT: " << x.CT << endl << "TA: " << x.TA << endl << "TC: " << x.TC << endl << endl;
int res = 0;
int temp = min(x.AT, x.TA);
res += temp;
x.AT -= temp;
x.TA -= temp;
temp = min(x.AC, x.CA);
res += temp;
x.AC -= temp;
x.CA -= temp;
temp = min(x.CT, x.TC);
res += temp;
x.CT -= temp;
x.TC -= temp;
temp = min({x.AC, x.CT, x.TA});
res += temp*2;
x.AC -= temp;
x.CT -= temp;
x.TA -= temp;
temp = min({x.AT, x.TC, x.CA});
res += temp*2;
return res;
}
