#include "Anna.h"
#include <bits/stdc++.h>
using namespace std;
namespace Anna{
mt19937 rng(69420);
const int LEN=19;
int n;
string s;
vector<string> v[3]{
{"BB", "GG", "RR"},
{"BG", "GR", "RB"},
{"BR", "RG", "GB"},
};
pair<string, int> solve(int _n, string _s){
n=_n, s=_s;
if (n<LEN*2+1){
string ans;
for (int i=0; i<n; ++i) if (s[i]=='B') ans.push_back('G'); else ans.push_back('B');
return {ans, n};
}
string s2;
while ((int)s2.size()<n/2){
s2.push_back(rng()%3+'0');
}
string ans;
for (int i=0; i<n/2; ++i){
int id=s2[i]-'0';
for (auto &t:v[id]){
if (t[0]!=s[i<<1] && t[1]!=s[i<<1|1]){
ans+=t;
break;
}
}
}
if ((int)ans.size()!=n){
if (s.back()=='B') ans.push_back('G');
else ans.push_back('B');
}
return {ans, LEN*2+1};
}
}
pair<string, int> anna(int N, string S) {
return Anna::solve(N, S);
}
#include "Bruno.h"
#include <bits/stdc++.h>
using namespace std;
namespace Bruno{
mt19937 rng(69420);
const int LEN=19;
bool small;
map<string, int> mp;
int n;
vector<string> v[3]{
{"BB", "GG", "RR"},
{"BG", "GR", "RB"},
{"BR", "RG", "GB"},
};
void init(int _n){
n=_n;
string s2;
while ((int)s2.size()<n/2){
s2.push_back(rng()%3+'0');
}
for (int i=0; i+LEN<=(int)s2.size(); ++i){
mp[s2.substr(i, LEN)]=i<<1|1;
}
}
int solve(string s){
string s1, s2;
for (int i=0; i<LEN*2; i+=2){
for (int j=0; j<3; ++j) for (auto &k:v[j]) if (k[0]==s[i] && k[1]==s[i+1]){
s1.push_back(j+'0');
}
}
for (int i=1; i<LEN*2+1; i+=2){
for (int j=0; j<3; ++j) for (auto &k:v[j]) if (k[0]==s[i] && k[1]==s[i+1]){
s2.push_back(j+'0');
}
}
if (mp.count(s1)) return mp[s1];
return mp[s2]-1;
}
}
void init(int N, int l) {
if (N==l) Bruno::small=1;
else Bruno::init(N);
}
int bruno(string u) {
if (Bruno::small) return 1;
return Bruno::solve(u);
}
