#include "gift.h"
#include <bits/stdc++.h>
std::set<std::pair<int,int>> set;
std::vector<std::pair<int,int>> check;
std::vector<std::pair<int,int>> merge;
int arr[500050];
std::string ans;
int prefa[500050];
int prefb[500050];
bool checkrange(int a,int b){
auto itr = set.upper_bound({a,a});
//std::cout << a << ' ' << b << ' ' << itr->first << ' ' << itr->second << '\n';
if(b < itr->first || itr==set.end()){
set.insert({a,b});
return true;
}
else{
auto p = *itr;
set.erase(itr);
p.second = std::max(p.second, b);
checkrange(a,p.second);
}
return false;
}
int construct(int n, int r, std::vector<int> a, std::vector<int> b, std::vector<int> x) {
for(int i=0;i<r;i++){
if(x[i]>2 || x[i]<1)return 0;
if(x[i]==1)
merge.push_back({a[i],b[i]});
if(x[i]==2)
check.push_back({a[i],b[i]});
}
std::sort(merge.rbegin(),merge.rend());
for(auto [l,r]:merge){
//std::cout << l << ' ' << r << '\n';
checkrange(l,r);
}
int numset = 1;
for(auto [l,r]:set){
//std::cout << l << ' ' << r << '\n';
for(int i=l;i<=r;i++){
arr[i]=numset;
}
numset++;
}
ans.push_back('R');
prefa[0]=1;
prefb[0]=0;
for(int i=1;i<n;i++){
if(arr[i]==0||arr[i]!=arr[i-1]){
if(ans[i-1]=='R')ans.push_back('B');
if(ans[i-1]=='B')ans.push_back('R');
}
else{
ans.push_back(ans[i-1]);
}
prefa[i]=prefa[i-1];
prefb[i]=prefb[i-1];
if(ans.back()=='R')prefa[i]+=1;
if(ans.back()=='B')prefb[i]+=1;
}
for(auto [l,r]:check){
int A,B;
if(l!=1)
A = prefa[r]-prefa[l-1];
else
A = prefa[r];
if(l!=1)
B = prefb[r]-prefb[l-1];
else
B = prefb[r];
if(A==0||B==0)return 0;
}
craft(ans);
return 1;
}
