Дано целое неотрицательное число \(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\), меньшего значения добиться невозможно.
Выходные данные
Для каждого набора входных данных выведите в отдельной строке:
- -1, если не существует искомой покраски;
- строку \(s\) из \(n\) символов, каждый из которых является буквой «R» или «B». Если \(i\)-я цифра числа \(x\) красится в красный цвет, то \(i\)-й символ строки \(s\) должен быть буквой «R», иначе буквой «B».
Число, которое образовано покрашенными в красный цвет цифрами, должно делится на \(A\). Число, которое образовано покрашенными в черный цвет цифрами, должно делится на \(B\). Значение \(|r-b|\) должно быть минимальным, где \(r\) — количество красных цифр, а \(b\) — количество чёрных. Если ответов несколько, то выведите любой из них.
Примечание
Первый набор входных данных разобран в условии.
Во втором наборе входных данных нет чётных цифр, поэтому невозможно составить число, которое делится на \(2\).
В третьем наборе входных данных любая покраска, содержащая хотя бы одну красную и одну чёрную цифру, подходит, поэтому можно покрасить \(4\) цифры в красный и \(4\) в чёрный (\(|4 - 4| = 0\), т. е. нельзя улучшить результат).
В четвёртом наборе входных данных существует единственная искомая покраска.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
5 3 13
02165
4 2 1
1357
8 1 1
12345678
2 7 9
90
|
RBRBR
-1
BBRRRRBB
BR
|