#include "Bruno.h"
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
mt19937 rnd2(228);
char to2(ll x) {
if (x == 0) {
return 'R';
}
if (x == 1) {
return 'G';
}
if (x == 2) {
return 'B';
}
return 'A';
}
ll from(char c) {
if (c == 'R') {
return 0;
}
if (c == 'G') {
return 1;
}
if (c == 'B') {
return 2;
}
return 3;
}
vector<ll> nums, nums2, no;
const ll COL1 = 4, COL2 = 9, V1 = 243, V2 = 59049;
vector<ll> arr[V1][V2];
void init(ll n, ll l) {
if (l < COL1 + COL2) {
return;
}
nums.resize(n);
nums2.resize(n);
no.resize(n);
for (ll i = 0; i < n; i++) {
nums[i] = rnd2() % 3;
nums2[i] = rnd2() % 2;
if (nums[i] == nums2[i]) {
nums2[i]++;
}
set<ll> all;
all.insert(0);
all.insert(1);
all.insert(2);
all.erase(nums[i]);
all.erase(nums2[i]);
no[i] = *all.begin();
}
for (ll i = 0; i + l <= n; i++) {
ll nxtCOL2 = 0;
for (ll j = 0; j < COL2; j++) {
nxtCOL2 *= 3;
nxtCOL2 += no[i + COL1 + j];
}
for (ll mask = 0; mask < (1 << COL1); mask++) {
ll now = 0;
for (ll j = 0; j < COL1; j++) {
now *= 3;
if ((mask >> j) & 1) {
now += nums[i + j];
} else {
now += nums2[i + j];
}
}
arr[now][nxtCOL2].push_back(i);
}
}
}
ll bruno(string u) {
if (u.size() < COL1 + COL2) {
return 1;
}
vector<ll> nn(u.size());
vector<ll> e1(u.size()), e2(u.size());
for (ll i = 0; i < u.size(); i++) {
nn[i] = from(u[i]);
set<ll> all;
all.insert(0);
all.insert(1);
all.insert(2);
all.erase(nn[i]);
e1[i] = *all.begin();
e2[i] = *all.rbegin();
}
ll firCOL1 = 0;
for (ll j = 0; j < COL1; j++) {
firCOL1 *= 3;
firCOL1 += nn[j];
}
vector<ll> allp;
for (ll mask = 0; mask < (1 << COL2); mask++) {
ll now = 0;
for (ll j = 0; j < COL2; j++) {
now *= 3;
if ((mask >> j) & 1) {
now += e1[COL1 + j];
} else {
now += e2[COL1 + j];
}
}
for (auto j : arr[firCOL1][now]) {
allp.push_back(j);
}
}
ll ans = -1;
ll best = u.size();
for (auto i : allp) {
bool b = true;
for (ll j = COL1 + COL2; j < u.size(); j++) {
if (nn[j] == no[i + j]) {
b = false;
break;
}
}
if (b) {
ll need = u.size() / 3;
for (ll j = 0; j < u.size(); j++) {
if (nn[j] == nums2[j]) {
need--;
}
}
if (assign_min(best, abs(need))) {
ans = i;
}
}
}
return ans + 1;
}