Adam 正在为 Bob 制作一条手工项链作为礼物。项链由 $n$ 颗珠子组成，从左到右编号为 $0$ 到 $n-1$。每颗珠子可以是红色或蓝色。Bob 给 Adam 发送了一份项链的需求列表。第 $i$ 个需求（$0 \le i < r$）规定，位置从 $a[i]$ 到 $b[i]$（包含两端）的珠子应该有 $x[i]$ 种不同的颜色。

请帮助 Adam 找到一种满足 Bob 所有需求的珠子排列方式，或者确定这是不可能的。

实现细节

你需要实现以下过程：

int construct(int n, int r, int[] a, int[] b, int[] x)

• $n$：珠子的数量。
• $r$：需求的数量。
• $a$：长度为 $r$ 的数组，表示每个需求的起始位置。
• $b$：长度为 $r$ 的数组，表示每个需求的结束位置。
• $x$：长度为 $r$ 的数组，表示每个需求所需的颜色种类数。
• 此过程将被调用恰好一次。
• 如果存在一种构造方式，该过程应恰好调用一次 craft 来报告构造结果，随后返回 $1$。
• 否则，该过程应返回 $0$，且不调用 craft。

你的程序应调用以下过程来报告构造结果：

void craft(string s)

• $s$：一个长度为 $n$ 的字符串，如果第 $j$ 颗珠子是红色，则 $s[j]$ 为 'R'；如果是蓝色，则为 'B'。

样例

样例 1

考虑以下调用：

construct(4, 2, [0, 2], [2, 3], [1, 2])

这意味着总共有 $4$ 颗珠子和 $2$ 个需求如下： 位置 $0$ 到 $2$ 应该有 $1$ 种颜色， 位置 $2$ 到 $3$ 应该有 $2$ 种颜色。

这可以通过将位置 $0$ 到 $2$ 的珠子染成红色，将位置 $3$ 的珠子染成蓝色来实现。

因此，construct 过程应进行以下调用：

craft("RRRB")

随后应返回 $1$。

在这种情况下，存在多种符合要求的构造方式，所有这些方式都被视为正确。

样例 2

考虑以下调用：

construct(3, 3, [0, 1, 0], [1, 2, 2], [1, 1, 2])

这意味着总共有 $3$ 颗珠子和 $3$ 个需求如下： 位置 $0$ 到 $1$ 应该有 $1$ 种颜色， 位置 $1$ 到 $2$ 应该有 $1$ 种颜色， * 位置 $0$ 到 $2$ 应该有 $2$ 种颜色。

在这种情况下，不存在满足所有要求的珠子排列方式。

因此，construct 过程应返回 $0$，且不调用 craft。

数据范围

• $1 \le n, r \le 500\,000$
• $0 \le a[i] \le b[i] \le n - 1$（对于所有 $0 \le i \le r - 1$）
• $1 \le x[i] \le 2$（对于所有 $0 \le i \le r - 1$）

子任务

1. (10 分) $x[i] = 1$（对于所有 $0 \le i \le r - 1$）
2. (15 分) $x[i] = 2$（对于所有 $0 \le i \le r - 1$）
3. (20 分) $1 \le n, r \le 18$
4. (25 分) $1 \le n, r \le 2000$
5. (30 分) 无附加限制。

样例评测程序

样例评测程序按以下格式读取输入：

• 第 $1$ 行：$n \ r$
• 第 $2+i$ 行（$0 \le i \le r-1$）：$a[i] \ b[i] \ x[i]$

样例评测程序按以下格式打印你的答案：

• 第 $1$ 行：construct 的返回值。
• 第 $2$ 行：$s$
• 如果 construct 的返回值为 $0$，则不会打印 $s$。