Задача C. Ископаемая арифметика ≡

Условие

Археологическая экспедиция обнаружила в долине реки Амазонка следы доселе неизвестной цивилизации индейцев. На стенах крупнейшего храмового комплекса исследователи обнаружили надписи, которые при ближайшем рассмотрении оказались записями чисел.

Анализ следов письменности позволил археологам определить, что индейцы использовали натуральные числа в диапазоне от 1 до 2^N. Запись любого числа состояла из ровно N знаков двух видов. За сходство с латинскими буквами ученые назвали один из знаков Q-символом, другой — R-символом, а саму запись — QR-записью.

Выяснилось также, что индейцы сравнивали числа в QR-записи по следующему правилу:

1. числа равны, если имеют идентичную запись;
2. одно число меньше другого, если в записи первого количество R-символов меньше, чем в записи второго;
3. при равном количестве R-символов числа сравниваются как строки (при этом Q-символ считается меньше R-символа).

Для облегчения работы археологам необходима программа для перевода натуральных чисел в QR-запись.

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

2 1

QQ

3 5

QRR