#include <string>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
vector<map<string, int> > prefPairs {
{
{"AA", 0},
{"AC", 0},
{"AT", 0},
{"CC", 0},
{"CA", 0},
{"CT", 0},
{"TT", 0},
{"TA", 0},
{"TC", 0}
}
};
vector<map<char, int> > prefA = {{
{'A', 0},
{'C', 0},
{'T', 0},
}};
vector<map<char, int> > prefB = {{
{'A', 0},
{'C', 0},
{'T', 0},
}};
void init(string a, string b) {
prefA[0][a[0]]++;
prefB[0][b[0]]++;
string s;
s += a[0];
s += b[0];
prefPairs[0][s]++;
for(int i = 1; i < a.size(); i++) {
prefA.push_back(prefA[i-1]);
prefA[i][a[i]]++;
prefB.push_back(prefB[i-1]);
prefB[i][b[i]]++;
prefPairs.push_back(prefPairs[i-1]);
s = "";
s += a[i];
s += b[i];
prefPairs[i][s]++;
}
}
int get_distance(int x, int y) {
for (const auto& [key,value] : prefA[0]) {
if(x > 0) {
if (prefA[y][key] - prefA[x-1][key] != prefB[y][key] - prefB[x-1][key]) return -1;
continue;
}
if (prefA[y][key] != prefB[y][key]) return -1;
}
int moves = 0;
map<string,int> current = prefPairs[y];
if(x > 0) {
for(const auto& [key,value] : prefPairs[x-1]) {
current[key] -= value;
}
}
int total = 0;
for(const auto& [key,value] : current) {
if (key == "AA" || key == "CC" || key == "TT") continue;
total += value;
}
total -= abs(current["AC"] - current["CA"]) & ~1;
moves += abs(current["AC"] - current["CA"])>>1;
total -= abs(current["AT"] - current["TA"]) & ~1;
moves += abs(current["AT"] - current["TA"])>>1;
total -= abs(current["CT"] - current["TC"]) & ~1;
moves += abs(current["CT"] - current["TC"])>>1;
moves += (total/3)*2;
total %= 3;
//if (total == 1) {
// cout << "Not good" << endl;
//}
if(total) {
moves++;
}
return moves;
}
/*
int main() {
int n, q; cin >> n >> q;
string a, b; cin >> a >> b;
init(a,b);
cout << get_distance(1, 2) << endl;
for(const auto& m : prefPairs) {
for(const auto& [key,value] : m) {
cout << key << " " << value << endl;
}
cout << "\n\n\n\n";
}
return 0;
}
*/
