#include "gift.h"
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn=5e5+5;
const string s="RB";
const int Log=19, pot=(1<<Log);
int t1[pot*2], t2[pot*2];
void update(int x, int val){
t1[x]=t2[x]=val;
for(x/=2; x>0; x/=2){
t1[x]=max(t1[x*2], t1[x*2+1]);
t2[x]=min(t2[x*2], t2[x*2+1]);
}
}
pair < int, int > query(int L, int D, int x, int l, int d){
if(L>=l && D<=d){
return {t1[x], t2[x]};
}
pair < int, int > lijeva={0, 1}, desna={0, 1};
if((L+D)/2>=l){
lijeva=query(L, (L+D)/2, x*2, l, d);
}
if((L+D)/2+1<=d){
desna=query((L+D)/2+1, D, x*2+1, l, d);
}
return {max(lijeva.first, desna.first), min(lijeva.second, desna.second)};
}
int poz[maxn];
int neg[maxn];
string sol;
int construct(int n, int r, vector<int> a, vector<int> b, vector<int> x) {
for(int i=0; i<r; i++){
if(x[i]==1){
poz[a[i]]++;
neg[b[i]+1]++;
}
}
int sw=0;
bool pp=0;
for(int i=0; i<n; i++){
sw-=neg[i];
if(!sw){
pp^=1;
}
sw+=poz[i];
update(i+pot, pp);
sol.push_back(s[pp]);
}
pair < int, int > p;
for(int i=0; i<r; i++){
if(x[i]==2){
p=query(0, pot-1, 1, a[i], b[i]);
if(p.first==p.second){
return 0;
}
}
}
craft(sol);
return 1;
}
