Red-Black Number
Contest: Codeforces Round 748 (Div. 3)
Difficulty rating: 2100
Tags: dfs and similar, dp, implementation, math, meet-in-the-middle

It is given a non-negative integer $$$x$$$, the decimal representation of which contains $$$n$$$ digits. You need to color each its digit in red or black, so that the number formed by the red digits is divisible by $$$A$$$, and the number formed by the black digits is divisible by $$$B$$$.

At least one digit must be colored in each of two colors. Consider, the count of digits colored in red is $$$r$$$ and the count of digits colored in black is $$$b$$$. Among all possible colorings of the given number $$$x$$$, you need to output any such that the value of $$$|r - b|$$$ is the minimum possible.

Note that the number $$$x$$$ and the numbers formed by digits of each color, may contain leading zeros.

Example of painting a number for $$$A = 3$$$ and $$$B = 13$$$

The figure above shows an example of painting the number $$$x = 02165$$$ of $$$n = 5$$$ digits for $$$A = 3$$$ and $$$B = 13$$$. The red digits form the number $$$015$$$, which is divisible by $$$3$$$, and the black ones — $$$26$$$, which is divisible by $$$13$$$. Note that the absolute value of the difference between the counts of red and black digits is $$$1$$$, it is impossible to achieve a smaller value.

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 10$$$) — the number of test cases. Then $$$t$$$ test cases follow.

Each test case consists of two lines. The first line contains three integers $$$n$$$, $$$A$$$, $$$B$$$ ($$$2 \le n \le 40$$$, $$$1 \le A, B \le 40$$$). The second line contains a non-negative integer $$$x$$$ containing exactly $$$n$$$ digits and probably containing leading zeroes.

Output format:
For each test case, output in a separate line:

- -1 if the desired coloring does not exist;
- a string $$$s$$$ of $$$n$$$ characters, each of them is a letter 'R' or 'B'. If the $$$i$$$-th digit of the number $$$x$$$ is colored in red, then the $$$i$$$-th character of the string $$$s$$$ must be the letter 'R', otherwise the letter 'B'.

The number formed by digits colored red should divisible by $$$A$$$. The number formed by digits colored black should divisible by $$$B$$$. The value $$$|r-b|$$$ should be minimal, where $$$r$$$ is the count of red digits, $$$b$$$ is the count of black digits. If there are many possible answers, print any of them.

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

Note:
The first test case is considered in the statement.

In the second test case, there are no even digits, so it is impossible to form a number from its digits that is divisible by $$$2$$$.

In the third test case, each coloring containing at least one red and one black digit is possible, so you can color $$$4$$$ digits in red and $$$4$$$ in black ($$$|4 - 4| = 0$$$, it is impossible to improve the result).

In the fourth test case, there is a single desired coloring.

Example input:
4
5 3 13
02165
4 2 1
1357
8 1 1
12345678
2 7 9
90

Example output:
RBRBR
-1
BBRRRRBB
BR

Editorial:
The number $$$x$$$ is divisible by the number $$$y$$$ if and only if $$$x \equiv 0$$$ modulo $$$y$$$.
To solve this problem, let's use the concept of dynamic programming. There will be four states: the number of considered digits of the number $$$x$$$, the number of such considered digits that we have colored red, the remainder from dividing the red number by $$$A$$$ and the black one by $$$B$$$. The value corresponding to the state will be described by three parameters: the possibility of a situation described by the states, the color of the last digit, and the parent state. Let's assume that the number that contains $$$0$$$ digits is equal to $$$0$$$.
Initially, let's mark the state in which $$$0$$$ digits are considered, of which $$$0$$$ are red digits, and both remainders are equal to $$$0$$$, as possible. Next, let's iterate over all states in the following order: first by the number of considered digits, then by the number of considered red digits, then by the remainder of the division by $$$A$$$ and by $$$B$$$. From the current state, if it is possible (i.e. the corresponding mark is set), you can make two transitions to new states. At the first transition, we paint the last digit in red, at the second one in black. We need also to store the current state in the new states as the previous one.
A solution exists if and only if some state in which exactly $$$n$$$ digits are considered, of which at least $$$1$$$ and at most $$$n - 1$$$ red digits, and the remainders are equal to $$$0$$$, is marked as possible. Let's find such a state. Using the stored information about the color of the last digit and the previous state, we can restore the colors of all digits of the number $$$x$$$.