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