#include "gift.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ordered_set <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_multiset <int, null_type, less_equal <int>, rb_tree_tag, tree_order_statistics_node_update>
#define pii pair <int, int>
#define tiii tuple <int, int, int>
#define tiiii tuple <int, int, int, int>
#define emb emplace_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define iShowSpeed cin.tie(NULL)->sync_with_stdio(false)
#define matrix vector <vector <int>>
#define mat(n, m) vector <vector <int>> (n, vector <int> (m));
const int mod = 1e9 + 7;
const int inf = 1e9;
const matrix II = {{1, 0}, {0, 1}};
const int N = 5e5 + 5;
int par[N];
int dsu(int a){
return par[a] = (a == par[a] ? a : dsu(par[a]));
}
int construct(int n, int r, vector<int> a, vector<int> b, vector<int> x) {
iota(par, par + N, 0ll);
int cnt[3] = {0};
for (int i = 0; i < r; i++) {
cnt[x[i]]++;
}
if (cnt[1] == r) {
string ss(n, 'R');
craft(ss);
return 1;
}
if (cnt[2] == r) {
string ss = "";
for (int i = 0; i < r; i++) if (a[i] == b[i]) return 0;
for (int i = 0; i < n; i++) {
if (i % 2) ss += "R";
else ss += "B";
}
craft(ss);
return 1;
}
string s(n, ' ');
vector <pii> interval;
for (int i = 0; i < r; i++) {
if (x[i] == 1) {
interval.emb(a[i], b[i]);
}
}
sort(all(interval));
vector <pii> lr;
for (auto [ll, rr] : interval) {
if (lr.empty() || lr.back().second < ll) lr.emb(ll, rr);
else lr.back().second = max(lr.back().second, rr);
}
for (auto [ll, rr] : lr) {
for (int i = ll; i < rr; i++) {
s[i] = 'R';
par[dsu(i)] = dsu(i + 1);
}
s[rr] = 'R';
}
for (int i = 0; i < r; i++) {
if (x[i] == 2) {
if (dsu(a[i]) == dsu(b[i])) return 0;
}
}
for (int i = 0; i < n; i++) {
if (s[i] != ' ') continue;
int j = i, idx = 0;
while (j < n && s[j] == ' ') {
if (idx % 2 == 0) s[j] = 'B';
else s[j] = 'R';
idx++;
j++;
}
if (s[j - 1] == 'R') s[j - 1] = 'B';
i = j - 1;
}
craft(s);
return 1;
}
/*
sub 1: x[i] = 1
just output all "R"
sub 2: x[i] = 2
if (a[i] == b[i]) : return 0;
else return alternating sequence
sub 3: 1 <= n,r <= 18
sub 4: 1 <= n,r <= 2000
sub 5: full sol
*/
