CF1593F.Red-Black Number

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.

给定一个非负整数 $x$，其十进制表示包含 $n$ 位数字。你需要将 $x$ 的每一位数字染成红色或黑色，使得所有红色数字按原顺序组成的数能被 $A$ 整除，所有黑色数字按原顺序组成的数能被 $B$ 整除。

每种颜色（红与黑）都至少需染一个数字。设红色数字的个数为 $r$，黑色数字的个数为 $b$。在所有满足条件的染色方案中，你需要输出任意一种使得 $|r - b|$ 尽可能小的方案。

注意：整数 $x$ 以及由每种颜色的数字所组成的数均允许包含前导零。

当 $A = 3$ 且 $B = 13$ 时对一个数字进行染色的示例

上图展示了对 $n = 5$ 位数字 $x = 02165$ 进行染色的一个示例（对应 $A = 3$，$B = 13$）。红色数字组成数字 $015$，可被 $3$ 整除；黑色数字组成数字 $26$，可被 $13$ 整除。注意，红色与黑色数字个数之差的绝对值为 $1$，这是无法进一步减小的。

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.

第一行包含一个整数 $t$（$1 \le t \le 10$）——测试用例的数量。随后是 $t$ 个测试用例。

每个测试用例由两行组成。第一行包含三个整数 $n$、$A$、$B$（$2 \le n \le 40$，$1 \le A, B \le 40$）。第二行包含一个非负整数 $x$，该整数恰好有 $n$ 位数字，且可能包含前导零。

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.

对于每个测试用例，在单独的一行中输出：

• 若不存在满足要求的染色方案，则输出 -1；
• 否则输出一个长度为 $n$ 的字符串 $s$，其中每个字符为字母 'R' 或 'B'。若数字 $x$ 的第 $i$ 位数字被染成红色，则字符串 $s$ 的第 $i$ 个字符必须是 'R'，否则为 'B'。

由红色数字构成的数应能被 $A$ 整除；由黑色数字构成的数应能被 $B$ 整除。令 $r$ 表示红色数字的个数，$b$ 表示黑色数字的个数，则 $|r-b|$ 应尽可能小。若存在多个满足条件的答案，输出任意一个即可。

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.

题目陈述中已考虑第一个测试用例。

在第二个测试用例中，不存在偶数数字，因此无法用其数字构成一个能被 $2$ 整除的数。

在第三个测试用例中，所有至少包含一个红色数字和一个黑色数字的染色方案均是可行的，因此你可以将 $4$ 个数字染成红色、$4$ 个染成黑色（此时 $|4 - 4| = 0$，结果已无法进一步优化）。

在第四个测试用例中，仅存在一种满足要求的染色方案。