Ferries (Hard)

One day a group of friends jumped into their $2n$ cars and went on a road trip into the lake district. The cars were numbered 1 through $2n$. At the start they were driving in this order.

During the trip the convoy met several ferries, one after another. Each ferry was exactly large enough to hold all $2n$ cars, and no other cars were around at any time. Every time the cars used a ferry, their order got mixed up. The loading and unloading process causes this.

A ferry is a long, narrow boat with room for two columns of cars, each with $n$ cars. When loading, the first $n$ cars form the first column and the last $n$ cars form the second column. When unloading, all cars drive away at the same time, and they must zip together into a single convoy. The first car in the new order is the first car from the right column. The second car is the first car from the left column. The third car is the second car from the right column, and so on, alternating between right and left.

Above: Cars 1 through 6, in this order, just boarded a type-R ferry (from the bottom of the figure). The cars will leave this ferry in the following order: 1, 4, 2, 5, 3, 6.

There are two types of ferries. On type-L ferries the crew instructs the cars to fill the Left column first. On type-R ferries the cars fill the Right column first. The ferry type does not affect how the cars leave. The first car to leave is always the first car in the right column.

The trip is now over. Your car was car $x$, so at the beginning it was the $x$-th car. You remember a sequence $a_1, \ldots, a_k$ of positive integers. The number $a_i$ means that at some point your car was the $a_i$-th car from the beginning of the convoy. The numbers are in chronological order: your car was in position $a_i$ before it was in position $a_i + 1$, for all $i$.

Compute the smallest possible number $f$ of ferries you encountered during the trip. Produce a proof as well: one possible sequence of exactly $f$ Ls and Rs, such that the $f$ ferries could have been type-L and type-R ferries in the given order.

The first line of the input file contains an integer $t = 100$, the number of test cases. Each test case is preceded by a blank line.

Each test case consists of two lines. The first line contains the integers $n$, $x$, and $k$, where $1 \le x \le 2n$. The second line contains the integers $a_1, \ldots, a_k$.

For each test case, output a single line with the number $f$, a colon, and one possible shortest string of Ls and Rs. There are no spaces in the output.

$1 \le n \le 10^{18}$

$1 \le k \le 10^4$

In the first example there were no ferries, so the car stayed in the first place.

In the second example the first type-L ferry moves the car to position 2, and the second type-L ferry moves it to position 4.

In the third example, RR moves the car from 2 to 5, L moves it from 5 to 3, RRL moves it from 3 to 1, and L moves it from 1 to 2.