| Codeforces Round 748 (Div. 3) |
|---|
| Закончено |
Дано целое неотрицательное число $$$x$$$, десятичная запись которого содержит $$$n$$$ цифр. Необходимо покрасить каждую его цифру в красный или чёрный цвет, так чтобы число, образуемое красными цифрами, делилось на $$$A$$$, а число, образуемое чёрными цифрами, делилось на $$$B$$$. Как в красный, так и в чёрный цвет должна быть покрашена хотя бы одна цифра. Из всех таких покрасок числа $$$x$$$, которые возможны, необходимо вывести любую такую, чтобы, если в красный покрашено $$$r$$$ цифр, а в чёрный — $$$b$$$ цифр, величина $$$|r - b|$$$ была минимально возможной.
Обратите внимание, что число $$$x$$$, а также числа, образуемые цифрами одного цвета, могут содержать ведущие нули.
Пример покраски числа для $$$A = 3$$$ и $$$B = 13$$$ На рисунке выше показан пример покраски числа $$$x = 02165$$$ из $$$n = 5$$$ цифр для $$$A = 3$$$ и $$$B = 13$$$. Красные цифры образуют число $$$015$$$, которое делится на $$$3$$$, а чёрные — $$$26$$$, которое делится на $$$13$$$. Заметим, что абсолютная величина разности количеств красных и чёрных цифр равна $$$1$$$, меньшего значения добиться невозможно.
В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 10$$$) — количество наборов входных данных. Далее следуют $$$t$$$ наборов входных данных.
Каждый набор входных данных состоит из двух строк. Первая строка содержит три целых числа $$$n$$$, $$$A$$$, $$$B$$$ ($$$2 \le n \le 40$$$, $$$1 \le A, B \le 40$$$). Вторая строка содержит целое неотрицательное число $$$x$$$, состоящее ровно из $$$n$$$ цифр и, возможно, содержащее ведущие нули.
Для каждого набора входных данных выведите в отдельной строке:
- -1, если не существует искомой покраски;
- строку $$$s$$$ из $$$n$$$ символов, каждый из которых является буквой «R» или «B». Если $$$i$$$-я цифра числа $$$x$$$ красится в красный цвет, то $$$i$$$-й символ строки $$$s$$$ должен быть буквой «R», иначе буквой «B».
Число, которое образовано покрашенными в красный цвет цифрами, должно делится на $$$A$$$. Число, которое образовано покрашенными в черный цвет цифрами, должно делится на $$$B$$$. Значение $$$|r-b|$$$ должно быть минимальным, где $$$r$$$ — количество красных цифр, а $$$b$$$ — количество чёрных. Если ответов несколько, то выведите любой из них.
4 5 3 13 02165 4 2 1 1357 8 1 1 12345678 2 7 9 90
RBRBR -1 BBRRRRBB BR
Первый набор входных данных разобран в условии.
Во втором наборе входных данных нет чётных цифр, поэтому невозможно составить число, которое делится на $$$2$$$.
В третьем наборе входных данных любая покраска, содержащая хотя бы одну красную и одну чёрную цифру, подходит, поэтому можно покрасить $$$4$$$ цифры в красный и $$$4$$$ в чёрный ($$$|4 - 4| = 0$$$, т. е. нельзя улучшить результат).
В четвёртом наборе входных данных существует единственная искомая покраска.
