32045번 - Sprinklers 서브태스크스페셜 저지다국어

Václav has a beautiful flower garden consisting of $M$ flowers planted on a single line. On this line, Václav has also placed $N$ sprinklers to water his flowers.

The positions of the sprinklers are given by the numbers $s_{1},\ldots,s_{N}$. The positions of the flowers are given by the numbers $f_{1},\ldots,f_{M}$. Both are provided 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}$

Václav is leaving for CEOI soon. He would like to make sure that all of his flowers are properly watered while he is away. To do this, he turns each sprinkler individually to the left or to the right, and sets their spraying power — all sprinklers share the same water hose, and therefore spray the same distance.

If the spraying power is $K$ and the $i$-th sprinkler is turned to the left, it will water all flowers with positions between $s_{i} - K$ and $s_{i}$ (inclusive). Similarly, if the $j$-th sprinkler is turned to the right, it will water all flowers with positions between $s_{j}$ and $s_{j} + K$ (inclusive). A single sprinkler can water multiple flowers and a single flower can be watered by multiple sprinklers.

Your task is to decide whether it's possible to water all the flowers. If so, you should find the minimum sufficient spraying power, along with a corresponding configuration of sprinklers. If there exist multiple valid configurations with minimal spraying power, output any of them.

The first line of input contains two integers: $N$ and $M$, separated by a space. The second line contains $N$ space-separated integers $s_{1},\ldots,s_{N}$ — the positions of the sprinklers. The third line contains $M$ space-separated integers $f_{1},\ldots,f_{M}$ — the positions of the flowers.

If it is not possible to water all the flowers, print the number $-1$.

If it is possible, the output should consist of two lines. On the first line, output the number $K$ – the minimum spraying power required to water all the flowers. On the second line, print a string $c$ of length $N$, such that $c_i$ is L if the $i$-th sprinkler should be turned to the left and R otherwise.

• $1 \leq N,M \leq 10^5$
• $0 \leq s_{i} \leq 10^9$ (for each $i$ such that $1 \leq i \leq N$)
• $0 \leq f_{i} \leq 10^9$ (for each $i$ such that $1 \leq i \leq M$)
• $s_{i} \leq s_{j}$ for all $i \leq j$
• $f_{i} \leq f_{j}$ for all $i \leq j$