Задана строка \(s\) из строчных букв латинского алфавита. Требуется покрасить каждую букву в один из двух цветов (красный или синий) так, что если выписать все красные буквы слева направо и выписать все синие буквы слева направо, то лексикографически максимальная из двух выписанных строк будет как можно лексикографически меньше. Одинаковые буквы могут быть покрашены в разные цвета, то есть для каждого индекса в строке \(s\) можно выбрать любой из двух цветов.
Формально, выпишем
- строку \(r\) (может быть пустой) — все красные буквы в порядке слева направо (красная подпоследовательность),
- строку \(b\) (может быть пустой) — все синие буквы в порядке слева направо (синяя подпоследовательность).
Ваша задача придумать такую покраску, что \(\max(r, b)\) — минимален. Небольшое напоминание: пустая строка является лексикографически наименьшей.
Выходные данные
Выведите \(t\) строк, \(i\)-я из них должна содержать ответ на \(i\)-й набор входных данных. Выведите строку длины \(n\), где \(n\) — длина заданной строки \(s\): \(j\)-й символ строки должен быть равен либо 'R', либо 'B' в зависимости от того в красный или синий цвет покрашен \(j\)-й символ строки в найденном решении. Если ответов несколько, выведите любой из них.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
kotlin
codeforces
abacaba
ffccgc
yz
|
RRRRBB
RRRRRRRBBB
RRRRBBB
RBBBBR
RR
|