Bottle Arrangements
Contest: SWERC 2021-2022 - Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Tags: constructive algorithms

Gabriella has been instructed to organize a renowned wine tasting event which will be attended by $$$m$$$ critics. On display, there will be $$$n$$$ different varieties of wine, each of which can either be a red wine or a white wine.

The wines will come in $$$n$$$ bottles arranged in a line on the table, and, for convenience, each critic will sip from a contiguous interval of bottles: that is, he/she will taste exactly the bottles at position $$$a, \, a + 1, \, \dots, \, b$$$ for some $$$1 \le a \le b \le n$$$. The interval depends on the critic, who will select it on the spot according to their preferences. In fact, the $$$i$$$-th critic ($$$1 \le i \le m$$$) has requested that he/she wants to taste exactly $$$r_i$$$ red wines and $$$w_i$$$ white wines.

Gabriella has yet to choose how many bottles of red wine and white wine there will be, and in what order they will appear. Help her find an arrangement (that is, a sequence of $$$n$$$ bottles of either red or white wine) that satisfies the requests of all the critics, or state that no such arrangement exists.

Input format:
Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1\le t\le 100$$$) — the number of test cases. The descriptions of the $$$t$$$ test cases follow.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 100$$$, $$$1 \le m \le 100$$$) — the number of bottles of wine and the number of critics.

Each of the next $$$m$$$ lines contains two integers $$$r_i$$$ and $$$w_i$$$ ($$$0 \le r_i, \, w_i \le 100$$$, $$$r_i + w_i \ge 1$$$) — the number of red and white wines that the $$$i$$$-th critic wants to taste.

Output format:
For each test case, if at least one solution exists, print a string of length $$$n$$$ made up of the characters R and W, where the $$$j$$$-th character ($$$1 \le j \le n$$$) denotes the type of the wine in the $$$j$$$-th bottle of the arrangement (R for red and W for white). If there are multiple solutions, print any.

If no solution exists, print the string IMPOSSIBLE.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, there are $$$n = 5$$$ bottles of wine to be arranged and $$$m = 3$$$ critics. The arrangement RWRRW satisfies the requests of all three critics. Indeed:

- the first critic can choose the interval $$$[3, \, 3]$$$, which contains exactly one bottle of red wine (note that $$$[1, \, 1]$$$ and $$$[4, \, 4]$$$ are other valid choices);
- the second critic can choose the interval $$$[1, \, 5]$$$, which contains $$$3$$$ bottles of red wine and $$$2$$$ bottles of white wine;
- the third critic can choose the interval $$$[2, \, 5]$$$, which contains $$$2$$$ bottles of red wine and $$$2$$$ bottles of white wine.

Example input:
3
5 3
1 0
3 2
2 2
4 3
2 1
1 1
0 3
3 2
0 2
0 3

Example output:
RWRRW
IMPOSSIBLE
WWW

Editorial:
Let $$$r_{\max}$$$ be the maximum number of bottles of red wines requested by one critic, i.e., $$$r_{\max} = \max\{r_1, \, r_2, \, \dots, \, r_m\}$$$. Likewise, let $$$w_{\max}$$$ be the maximum number of white wines requested by one critic, i.e., $$$w_{\max} = \max\{w_1, \, w_2, \, \dots, \, w_m\}$$$. Then, one can notice that, if $$$r_{\max} + w_{\max} > n$$$, there is no valid arrangement, simply because $$$n$$$ bottles are not sufficient.
On the other hand, suppose that $$$r_{\max} + w_{\max} \le n$$$. In this case, it is not difficult to produce an arrangement that satisfies all the requests: for instance, one can have the first $$$r_{\max}$$$ bottles be red wines, and the remaining $$$n - r_{\max}$$$ be white wines (note that the number $$$n - r_{\max}$$$ is nonnegative under our hypothesis). Then, if the $$$i$$$-th critic has requested $$$r_i \le r_{\max}$$$ red wines and $$$w_i \le w_{\max}$$$ white wines, they can choose the interval starting at position $$$a = r_{\max} - r_i + 1$$$ and ending at position $$$b = r_{\max} + w_i$$$ (it can be noticed that both these positions are in the range $$$[1, \, n]$$$).
The algorithm simply iterates over all critics, finds the values of $$$r_{\max}$$$ and $$$w_{\max}$$$, checks whether their sum does not exceed $$$n$$$ and, if that is the case, produces a valid string such as the one described.
Both the runtime and used memory are $$$\mathcal O(n + m)$$$.