P10806 [CEOI 2024] Sprinklers

**This problem is translated from [CEOI 2024](https://ceoi2024.fi.muni.cz/) Day 2 T3「[Sprinklers](https://ceoi2024.fi.muni.cz/page/tasks/statements/sprinklers.pdf)」.** Vaclav has a beautiful garden, where he planted a row of $M$ flowers. Along this row, Vaclav also placed $N$ sprinklers to water the flowers. The sprinkler positions are given by numbers $s_1, s_2, \ldots , s_N$. The flower positions are given by numbers $f_1, f_2, \ldots , f_M$. Both sequences are in non-decreasing order, that is: - $s_1 \leq s_2 \leq \ldots \leq s_N$. - $f_1 \leq f_2 \leq \ldots \leq f_M$. Vaclav will soon leave to attend CEOI. He wants to make sure that all flowers will be watered properly while he is away. To do this, he can rotate each sprinkler individually to the left or to the right, and set their spray power. Since all sprinklers share the same water pipe, the spray range is the same for all of them. If the spray power is $K$ and the $i$-th sprinkler is rotated to the left, it will water all flowers at positions between $s_i - K$ and $s_i$. Similarly, if the $j$-th sprinkler is rotated to the right, it will water all flowers at positions between $s_j$ and $s_j + K$. One sprinkler can water multiple flowers, and one flower can be watered by multiple sprinklers. Your task is to decide whether it is possible to water all the flowers. If it is, you should find the smallest spray power that is sufficient, and a corresponding sprinkler configuration. If there are multiple valid configurations with the minimum spray power, output any one of them.

The first line contains two integers $N$ and $M$, separated by spaces. The second line contains $N$ integers $s_1, s_2, \ldots , s_N$, separated by spaces, representing the sprinkler positions. The third line contains $M$ integers $f_1, f_2, \ldots , f_M$, separated by spaces, representing the flower positions.

If it is impossible to water all flowers, output the number $-1$. If it is possible, the output should contain two lines. The first line outputs the number $K$, the minimum spray power needed to water all flowers. In the second line, output a string $c$ of length $N$, where $c_i$ is `L` if the $i$-th sprinkler should be rotated to the left, otherwise it is `R`.

**Sample Explanation 1** Each flower is watered by at least one sprinkler. A spray power smaller than $6$ is impossible, because the flower at position $16$ is at distance $6$ from the nearest sprinkler. **Sample Explanation 2** No matter how the sprinklers are oriented, at most one flower can be watered at a time. For all input data, it holds that: - $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)$. The detailed additional constraints and scores for subtasks are given in the table below. | Subtask | Additional Constraints | Score | | :--: | :--: | :--: | | $1$ | $N = 1$ | $3$ | | $2$ | $N = 3x$, where $x$ is an integer, and $s_{3i+1} = s_{3i+2} = s_{3i+3}\ (0 \leq i \leq x-1)$ (i.e., sprinklers are always placed in groups of three) | $6$ | | $3$ | $N \leq 10, M \leq 1\,000$ | $17$ | | $4$ | $K \leq 8$ (i.e., for all testdata, there exists a sprinkler configuration such that a spray power of at most $8$ is sufficient to water all flowers) | $27$ | | $5$ | No additional constraints | $47$ | Translated by ChatGPT 5