#include "Anna.h"

#include <bits/stdc++.h>

namespace A {

    std::string gen_string() {
        auto try_gen = [&](int seed) {
            std::mt19937 rnd(2086 + seed);
            const int l = 37;

            std::unordered_map<uint64_t, int> set;
            int mx = 0;
            std::string s;
            int cnt = 0;

            auto substr = [&](int i) -> uint64_t {
                uint64_t res = 0;
                for (int j = 0; j < l; j++) {
                    res |= uint64_t(s[i + j] - '0') << j;
                }
                return res;
            };
            for (int i = 0; i < 5e5 + 100 && cnt < 1e7; i++, cnt++) {
                if (s.size() == i) {
                    s += '-';
                }
                s[i] = "01"[rnd() % 100 < 35];
                if (i > 0 && s[i - 1] == '1' || i > 1 && s[i - 2] == '1') {
                    s[i] = '0';
                }
                if (l <= i) {
                    auto t = substr(i - l);
                    if (set[t] > 0) {
                        if (i > mx) {
                            mx = mx + 1000;
                        }
                        for (int j = 0; j < 7; j++) {
                            i--;
                            set[substr(i - l)]--;
                        }
                        i--;
                        continue;
                    }
                    set[t]++;
                }
            }
            {
                int64_t cnt = 0;
                for (auto [a, b] : set) {
                    cnt += std::max(0, b - 1);
                }
                std::cerr << cnt << "  ";
            }
            return s;
        };

        const int n = 5e5 + 5;
        for (int i = 0;; i++) {
            std::cerr << i << " ";
            auto s = try_gen(i);
            std::cerr << s.size() << "\n";
            if (s.size() >= n) {
                return s;
            }
        }
    }

    int fuck(char ch) {
        std::string s = "RGB";
        return std::find(s.begin(), s.end(), ch) - s.begin();
    }
    char fuck2(int i) {
        return "RGB"[i];
    }
}  // namespace A

std::pair<std::string, int> anna(int n, std::string S) {
    auto data = A::gen_string().substr(0, n);

    std::vector<std::array<int, 3>> dp(n, {-1, -1, -1});
    for (int i = 0; i < 3; i++) {
        if (A::fuck2(i) != S[0]) {
            dp[0][i] = -2;
        }
    }
    for (int i = 0; i + 1 < n; i++) {
        for (int a = 0; a < 3; a++) {
            for (int b = 0; b < 3; b++) {
                if (dp[i][a] == -1 || b == A::fuck(S[i + 1])) {
                    continue;
                }
                if (data[i] == '1') {
                    if (b != a) {
                        continue;
                    }
                    dp[i + 1][b] = a;
                } else {
                    if ((i == 0 || data[i - 1] != '1') && a == b) {
                        continue;
                    }
                    dp[i + 1][b] = a;
                }
            }
        }
    }

    std::string t(n, '-');
    for (int i = n - 1, c = std::find_if(dp[n - 1].begin(), dp[n - 1].end(), [&](auto ch) { return ch != -1; }) - dp[n - 1].begin(); i >= 0; i--) {
        t[i] = A::fuck2(c);
        c = dp[i][c];
    }

    return {t, std::min(n, 39)};
}

#include "Bruno.h"

#include <bits/stdc++.h>

namespace B {

    std::string gen_string() {
        auto try_gen = [&](int seed) {
            std::mt19937 rnd(2086 + seed);
            const int l = 37;

            std::unordered_map<uint64_t, int> set;
            int mx = 0;
            std::string s;
            int cnt = 0;

            auto substr = [&](int i) -> uint64_t {
                uint64_t res = 0;
                for (int j = 0; j < l; j++) {
                    res |= uint64_t(s[i + j] - '0') << j;
                }
                return res;
            };
            for (int i = 0; i < 5e5 + 100 && cnt < 1e7; i++, cnt++) {
                if (s.size() == i) {
                    s += '-';
                }
                s[i] = "01"[rnd() % 100 < 35];
                if (i > 0 && s[i - 1] == '1' || i > 1 && s[i - 2] == '1') {
                    s[i] = '0';
                }
                if (l <= i) {
                    auto t = substr(i - l);
                    if (set[t] > 0) {
                        if (i > mx) {
                            mx = mx + 1000;
                        }
                        for (int j = 0; j < 7; j++) {
                            i--;
                            set[substr(i - l)]--;
                        }
                        i--;
                        continue;
                    }
                    set[t]++;
                }
            }
            {
                int64_t cnt = 0;
                for (auto [a, b] : set) {
                    cnt += std::max(0, b - 1);
                }
                std::cerr << cnt << "  ";
            }
            return s;
        };

        const int n = 5e5 + 5;
        for (int i = 0;; i++) {
            std::cerr << i << " ";
            auto s = try_gen(i);
            std::cerr << s.size() << "\n";
            if (s.size() >= n) {
                return s;
            }
        }
    }

    int fuck(char ch) {
        std::string s = "RGB";
        return std::find(s.begin(), s.end(), ch) - s.begin();
    }

}  // namespace B

int n, l;
std::string str;
std::map<int, std::map<std::string_view, int>> map;

void init(int N, int L) {
    n = N, l = L;
    str = B::gen_string();
}

int find_str(std::string s) {
    auto vec = s;
    // for (int i = 0; i < s.size(); i += 2) {
    //     vec.push_back((B::fuck(s[i]) + B::fuck(s[i + 1])) % 3);
    // }
    auto& mp = map[vec.size()];
    if (mp.empty()) {
        for (int i = 0; i + vec.size() <= str.size(); i++) {
            mp[std::string_view(str.begin() + i, str.begin() + i + vec.size())] = i;
        }
    }
    int res = mp.contains(vec) ? mp[vec] : -1;
    return res;
}

int bruno(std::string u) {
    if (n == l) {
        return 1;
    }
    std::string t;
    for (int i = 2; i < u.size(); i++) {
        if (u[i - 1] != u[i] || u[i - 1] == u[i - 2]) {
            t += '0';
        } else {
            t += '1';
        }
    }
    int ind = find_str(t);
    assert(ind != -1);
    return ind;
}