#include <bits/stdc++.h>
#include "gift.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
const int INF = 2e9, N = 1e6+10, M = 1e9+7, LOG = 16;
const ll LINF = 1e18;
struct SegTree {
struct Node {
int sum, lzy;
Node(int sum = 0, int lzy = 0) : sum(sum), lzy(lzy) {}
};
vector<Node> t;
vector<int> lo, hi;
void init(int n) {
t.resize(n << 2); lo.resize(n << 2); hi.resize(n << 2);
build(1, 1, n);
}
void build(int k, int l, int r) {
lo[k] = l; hi[k] = r;
int m = (l + r) / 2;
if(l != r)
build(k << 1, l, m),
build(k << 1 | 1, m+1, r);
}
void push(int k) {
if(t[k].lzy) {
t[k].sum = hi[k] - lo[k] + 1;
if(lo[k] != hi[k])
t[k << 1].lzy = t[k << 1 | 1].lzy = t[k].lzy;
}
}
int qry(int x) { return qry(x, x); }
int qry(int l, int r, int k = 1) {
push(k);
if(l <= lo[k] && hi[k] <= r) return t[k].sum;
if(l > hi[k] || r < lo[k]) return 0;
return qry(l, r, k << 1) + qry(l, r, k << 1 | 1);
}
void upd(int l, int r, int k = 1) {
push(k);
if(l > hi[k] || r < lo[k]) return;
if(l <= lo[k] && hi[k] <= r) {
t[k].lzy = 1; push(k);
return;
}
upd(l, r, k << 1);
upd(l, r, k << 1 | 1);
}
};
int construct(int n, int r, std::vector<int> a, std::vector<int> b, std::vector<int> x) {
SegTree seg;
seg.init(n);
for(int i = 0; i < r; ++i) a[i]++, b[i]++;
for (int i = 0; i < r; i++) {
if(x[i] == 1) {
if(a[i] < b[i])
seg.upd(a[i]+1, b[i]);
}
}
for (int i = 0; i < r; i++) {
if(x[i] == 2) {
if(a[i] < b[i])
if(seg.qry(a[i]+1, b[i]) == b[i] - a[i])
return 0;
}
}
string s = "R";
for(int i = 1; i < n; ++i) {
if(seg.qry(i))
s.push_back(s.back());
else
s.push_back(s.back() == 'B' ? 'R' : 'B');
}
craft(s);
return 1;
}
