Codeforces Round 748 (Div. 3) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

dfs and similar

dp

implementation

math

meet-in-the-middle

*2100

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Red-Black Number

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputIt 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.

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

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

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.

Example

Input

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

Output

RBRBR -1 BBRRRRBB BR

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.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/13/2024 14:09:41 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|