#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define all(v) (v).begin(),(v).end()
string a,b;
char xx[10]={'A','A','A','C','C','C','T','T','T'};
char yy[10]={'A','C','T','A','C','T','A','C','T'};
vector<pair<int,pair<string,string>>>vt;
map<pair<char,char>,int>MP[100050];
void funk(vector<int>vtt){
string a,b;
for(int v:vtt){
a+=xx[v];
b+=yy[v];
}
string qa=a,qb=b;
sort(all(qa));
sort(all(qb));
if(qa!=qb){
return;
}
int ans=0;
string ca=a,cb=b;
while(a!=b){
for(int i=0;i<a.size();i++){
for(int j=i+1;j<b.size();j++){
if(a[i]!=b[i]&&a[j]!=b[j]){
if(a[i]==b[j]&&a[j]==b[i]){
swap(a[i],a[j]);
ans++;
}
}
}
}
for(int i=0;i<a.size();i++){
for(int j=i+1;j<b.size();j++){
if(a[i]!=b[i]&&a[j]!=b[j]){
if(b[i]==a[j]){
swap(a[i],a[j]);
ans++;
}
}
}
}
}
vt.pb({ans,{ca,cb}});
}
void init(std::string ax, std::string ay) {
a=ax,b=ay;
for(int i=0;i<9;i++){
funk({i});
}
for(int i=0;i<9;i++){
for(int j=i;j<9;j++){
funk({i,j});
}
}
for(int i=0;i<9;i++){
for(int j=i;j<9;j++){
for(int k=j;k<9;k++){
funk({i,j,k});
}
}
}
sort(all(vt));
for(int i=0;i<a.size();i++){
if(i>0){
MP[i]=MP[i-1];
}
MP[i][{a[i],b[i]}]++;
}
}
int get_distance(int l, int r) {
int a1=0,a2=0,a3=0,b1=0,b2=0,b3=0;
map<pair<char,char>,int>mp;
mp=MP[r];
if(l>0){
for(auto it=mp.begin();it!=mp.end();it++){
mp[it->F]-=MP[l-1][it->F];
}
}
for(auto it=mp.begin();it!=mp.end();it++){
char q=it->F.F;
int cost=it->S;
if(q=='A'){
a1+=cost;
}
else if(q=='C'){
a2+=cost;
}
else{
a3+=cost;
}
q=it->F.S;
if(q=='A'){
b1+=cost;
}
else if(q=='C'){
b2+=cost;
}
else{
b3+=cost;
}
}
if(a1!=b1||a2!=b2||a3!=b3){
return -1;
}
int ans=0;
for(int i=0;i<vt.size();i++){
string x=vt[i].S.F,y=vt[i].S.S;
int k=vt[i].F;
int cost=1e7;
for(int i=0;i<x.size();i++){
cost=min(cost,mp[{x[i],y[i]}]);
}
if(cost>0){
for(int i=0;i<x.size();i++){
mp[{x[i],y[i]}]-=cost;
}
ans+=cost*k;
}
}
for(auto it=mp.begin();it!=mp.end();it++){
ans+=it->S;
}
return ans;
}
