#include "Anna.h"
#include <iostream>
#include <cstring>

typedef long long ll;

using namespace std;

namespace
{
	const int MAXN = 5e5 + 10;
	int n, m;
	string pat = "0121";
	int val[MAXN];

	inline bool Check(int x)
	{
		string st = "";
		for (int i = 0, s = 1; i < 9; i++, s *= 3)
			st = (char)((x / s % 3) + '0') + st;
		for (int i = 0; i + 3 < 9; i++)
			if (st.substr(i, 4) == pat) return 0;
		return 1;
	}

	inline string GetS(int x, char s1, char s2)
	{
		for (int i = 0; i < 3; i++)
			if (i != s1 - '0')
				for (int j = 0; j < 3; j++)
					if (j != s2 - '0' && (i + j) % 3 == x)
					{
						string ret = ""; ret.push_back(i + '0'), ret.push_back(j + '0');
						return ret;
					}
		return "";
	}

	inline void Trans(string &s)
	{
		for (int i = 0; i < s.size(); i++)
			if (s[i] == '0') s[i] = 'R';
			else if (s[i] == '1') s[i] = 'G';
			else if (s[i] == '2') s[i] = 'B';
			else if (s[i] == 'R') s[i] = '0';
			else if (s[i] == 'G') s[i] = '1';
			else s[i] = '2';
	}
}

pair <string, int> anna(int N, string S)
{
	if (N <= 28)
	{
		Trans(S);
		for (int i = 0; i < N; i++)
			if (S[i] == '2') S[i] = '0';
			else S[i]++;
		Trans(S);
		return make_pair(S, N);
	}
	n = N, m = (n / 2 + 12) / 13;
	for (int i = 1, j = 0; i <= m; i++)
	{
		while (!Check(j)) j++;
		val[i] = j++;
	}
	int len = m * 26;
	while (S.size() < len) S.push_back('R');
	Trans(S);
	string ret;
	static int tmp[15]; int p = 0;
	for (int i = 1; i <= m; i++)
	{
		for (int j = 0, s = 1; j < 9; j++, s *= 3)
			tmp[j] = val[i] / s % 3;
		for (int j = 8; ~j; j--)
			ret = ret + GetS(tmp[j], S[p], S[p + 1]), p += 2;
		for (int j = 0; j < 4; j++)
			ret = ret + GetS(pat[j] - '0', S[p], S[p + 1]), p += 2;
	}
	ret.resize(n);
	Trans(ret);
	// cout << ret << "\n";
	return {ret, min(n, 28)};
}

#include "Bruno.h"
#include <iostream>
#include <cstring>
#include <map>

typedef long long ll;

using namespace std;

namespace
{
	const int MAXN = 5e5 + 10;
	int n, m;
	string pat = "0121";
	int val[MAXN];

	inline bool Check(int x)
	{
		string st = "";
		for (int i = 0, s = 1; i < 9; i++, s *= 3)
			st = (char)((x / s % 3) + '0') + st;
		for (int i = 0; i + 3 < 9; i++)
			if (st.substr(i, 4) == pat) return 0;
		return 1;
	}

	inline void Trans(string &s)
	{
		for (int i = 0; i < s.size(); i++)
			if (s[i] == '0') s[i] = 'R';
			else if (s[i] == '1') s[i] = 'G';
			else if (s[i] == '2') s[i] = 'B';
			else if (s[i] == 'R') s[i] = '0';
			else if (s[i] == 'G') s[i] = '1';
			else s[i] = '2';
	}

	string ori;
	map <string, int> mp;

	bool FLAG;
}

void init(int N, int l)
{
	if (l == N) { FLAG = 1; return; }
	n = N, m = (n / 2 + 12) / 13;
	for (int i = 1, j = 0; i <= m; i++)
	{
		while (!Check(j)) j++;
		val[i] = j++;
	}
	for (int i = 1; i <= m; i++)
	{
		string st = "";
		for (int i = 0, s = 1; i < 9; i++, s *= 3)
			st = (char)((val[i] / s % 3) + '0') + st;
		ori = ori + st + pat;
	}
	ori.resize(n / 2);
	// cout << ori << '\n';
	if (n / 2 < 13) mp[ori] = 0;
	// cout << ori << "\n";
	for (int i = 0; i + 12 < n / 2; i++)
		mp[ori.substr(i, 13)] = i << 1;
}

int bruno(string str)
{
	if (FLAG) return 1;
	Trans(str);
	// cout << str << "\n";
	for (int _ = 0; _ < 2; _++)
	{
		string cur = "";
		for (int i = 1, p = 0; i <= 13 && 2 * i <= str.size(); i++)
		{
			int c = str[p + _] - '0' + str[p + 1 + _] - '0';
			cur.push_back(c % 3 + '0'), p += 2;
		}
		// cout << cur << "\n";
		if (mp.find(cur) != mp.end()) return mp[cur] - _ + 1;
		// string rep = cur + cur; int pos = -1;
		// for (int i = 0; i + 3 < rep.size(); i++)
		// 	if (rep.substr(i, 4) == pat) { pos = i; break; }
		// if (pos == -1) continue;
	}
	return 1;
}