P10806 [CEOI 2024] 洒水器

**题目译自 [CEOI 2024](https://ceoi2024.fi.muni.cz/) Day2 T3「[Sprinklers](https://ceoi2024.fi.muni.cz/page/tasks/statements/sprinklers.pdf)」** 瓦茨拉夫有一个美丽的花园，花园里种了一排 $M$ 朵花。在这一排上，瓦茨拉夫还放置了 $N$ 个洒水器来浇花。 洒水器的位置由数字 $s_1, s_2, \ldots , s_N$ 给出。花的位置由数字 $f_1, f_2, \ldots , f_M$ 给出。两者都是非递减顺序，即： - $s_1 \leq s_2 \leq \ldots \leq s_N$ - $f_1 \leq f_2 \leq \ldots \leq f_M$ 瓦茨拉夫很快就要去参加 CEOI 了。他想确保在他离开期间所有的花都能得到适当的浇水。为此，他可以单独将每个洒水器向左或向右旋转，并设置它们的喷水强度——所有洒水器共享同一个水管，因此喷射距离相同。 如果喷水强度为 $K$，并且第 $i$ 个洒水器向左旋转，它将浇灌位置在 $s_i - K$ 到 $s_i$ 之间的所有花。类似地，如果第 $j$ 个洒水器向右旋转，它将浇灌位置在 $s_j$ 到 $s_j+K$ 之间的所有花。单个洒水器可以浇灌多朵花，一朵花也可以被多个洒水器浇灌。 你的任务是决定是否可以浇灌所有的花。如果是，你应该找到最小的足够喷水强度，以及相应的洒水器配置。如果存在多个具有最小喷水强度的有效配置，输出其中任何一个。

输入的第一行包含两个用空格隔开的整数 $N$ 和 $M$。第二行包含 $N$ 个空格分隔的整数 $s_1, s_2, \ldots , s_N$，表示洒水器的位置。第三行包含 $M$ 个空格分隔的整数 $f_1, f_2, \ldots , f_M$，表示花的位置。

如果无法浇灌所有的花，则输出数字 $-1$。 如果可以，输出应该包含两行。第一行输出数字 $K$，表示浇灌所有花所需的最小的喷水强度。在第二行，输出长度为 $N$ 的字符串 $c$，其中 $c_i$ 为 `L`，如果第 $i$ 个洒水器应该向左旋转，否则为 `R`。

**样例解释 1** 每朵花至少被一个洒水器浇水。喷水强度低于 $6$ 是不可能的，因为位置 $16$ 的花离最近的洒水器有 $6$ 个单位距离。 **样例解释 2** 无论洒水器的方向如何，一次最多只能浇灌一朵花。 对于所有输入数据，满足： - $1 \leq N,M \leq 10^5$ - $0 \leq s_{i} \leq 10^9\ (1 \leq i \leq N)$ - $0 \leq f_{i} \leq 10^9\ (1 \leq i \leq M)$ - $s_{i} \leq s_{j}\ (i \leq j)$ - $f_{i} \leq f_{j}\ (i \leq j)$ 详细子任务附加限制及分值如下表所示。 | 子任务 | 附加限制 | 分值 | | :--: | :--: | :--: | | $1$ | $N = 1$ | $3$ | | $2$ | $N = 3x$，$x$ 是一个整数，$s_{3i+1}=s_{3i+2}=s_{3i+3}\ (0 \leq i \leq x-1)$（即洒水器总是成组放置三个）| $6$ | | $3$ | $N \leq 10, M \leq 1\,000$| $17$ | | $4$ | $K\leq 8$（即在所有测试数据中，存在一种洒水器配置，使得喷水强度最多为 $8$ 就足以浇灌所有的花） | $27$ | | $5$ | 无附加限制| $47$ |