#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 5; int pref[N], cnt[2][N][3]; char c[3] = {'A', 'C', 'T'}; int get_distance(int l, int r) { ++l, ++r; for (int i = 0; i < 3; i++) { if ((cnt[0][r][i] - cnt[0][l - 1][i]) != (cnt[1][r][i] - cnt[1][l - 1][i])) { return -1; } } return (pref[r] - pref[l - 1] + 1) / 2; } void init(string a, string b) { int n = (int) a.size(); for (int i = 0; i < n; i++) { pref[i + 1] = pref[i] + (a[i] != b[i] ? 1 : 0); for (int j = 0; j < 3; j++) { cnt[0][i + 1][j] += cnt[0][i][j]; cnt[1][i + 1][j] += cnt[1][i][j]; cnt[0][i + 1][j] += a[i] == c[j]; cnt[1][i + 1][j] += b[i] == c[j]; } } }