#include "gift.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef vector<int> vi;
struct q{
int l, r, type;
q(int a = 0, int b = 0, int c = 0){
l = a; r = b; type = c;
}
};
const bool customSort(q & a, q & b){
return a.type < b.type;
}
void update(int i, int ql, int qr, int l, int r, vi & tree, vi & lazy){
if(l >= ql && r <= qr){
tree[i] = r - l + 1;
if(l == r) return;
lazy[i*2] = 1;
lazy[i*2 + 1] = 1;
return;
}
if(l > qr || r < ql) return;
update(i*2, ql, qr, l, (l + r)/2, tree, lazy);
update(i*2 + 1, ql, qr, (l + r)/2 + 1, r, tree, lazy);
}
int query(int i, int ql, int qr, int l, int r, vi & tree, vi & lazy){
if(lazy[i]){
lazy[i] = 0;
tree[i] = r - l + 1;
if(l != r){
lazy[i*2] = 1;
lazy[i*2 + 1] = 1;
}
}
if(l >= ql && r <= qr) return tree[i];
if(l > qr || r < ql) return 0;
int q1 = query(i*2, ql, qr, l, (l + r)/2, tree, lazy);
int q2 = query(i*2 + 1, ql, qr, (l + r)/2 + 1, r, tree, lazy);
return q1 + q2;
}
void finish(int i, int l, int r, vi & tree){
if(tree[i]){
int toRem = min(tree[i], (r - l + 1)/2);
tree[i] -= toRem;
tree[i*2] = max(toRem, tree[i*2]);
tree[i*2 + 1] = max(tree[i*2 + 1], tree[i]);
}
if(l == r) return;
finish(i*2, l, (l + r)/2, tree);
finish(i*2 + 1, (l + r)/2 + 1, r, tree);
}
int construct(int n, int r, vector<int> a, vector<int> b, vector<int> x) {
vector<q> queries(r);
for (int i = 0; i < r; i++)
{
queries[i] = q(a[i] + 1, b[i] + 1, x[i]);
}
sort(queries.begin(), queries.end(), customSort);
int power2 = 1;
while(power2 < n) power2 *= 2;
int treeSize = 2*power2 - 1;
vi segTree(treeSize + 1, 0);
vi lazy(treeSize + 1, 0);
bool pos = true;
for (int i = 0; i < r; i++)
{
q cur = queries[i];
if(cur.type == 1){
update(1, cur.l, cur.r, 1, power2, segTree, lazy);
} else {
int sum = query(1, cur.l, cur.r, 1, power2, segTree, lazy);
if(sum == cur.r - cur.l + 1) pos = false;
}
}
finish(1, 1, power2, segTree);
for (int i = 1; i <= treeSize; i++)
{
cerr << segTree[i] << " ";
}
cerr << '\n';
if(pos){
string ans;
for (int i = 1; i <= n; i++)
{
ans.pb((segTree[i + treeSize/2] == 1 ? 'R' : 'B'));
}
craft(ans);
return 1;
}
return 0;
}
