#include "Anna.h"
#include<bits/stdc++.h>

using namespace std;

typedef int ll;

mt19937 rnd(228);

const ll len = 90;

char to(ll x) {
	if (x == 0) {
		return 'R';
	}
	if (x == 1) {
		return 'G';
	}
	if (x == 2) {
		return 'B';
	}
	return 'A';
}

pair<string, ll> anna(ll n, string s) {
	string ans(n, 'A');
	vector<ll> nums(n), nums2(n);
	for (ll i = 0; i < n; i++) {
		nums[i] = rnd() % 3;
		nums2[i] = rnd() % 2;
		if (nums2[i] == nums[i]) {
			nums2[i]++;
		}
	}
	for (ll i = 0; i < n; i++) {
		if (to(nums[i]) == s[i]) {
			ans[i] = to(nums2[i]);
		} else {
			ans[i] = to(nums[i]);
		}
	}
	return make_pair(ans, min(n, len));
}

#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 (best > abs(need)) {
				best = abs(need);
				ans = i;
			}
		}
	}
	return ans + 1;
}