Задача A. Код Грея ≡

Условие

Дана строка, состоящая из N символов 0 и 1. Требуется построить последовательность из всех возможных строк длиной N, состоящих из 0 и 1, такую что:

• первая строка последовательности — входная строка;
• каждая строка входит в последовательность один раз;
• соседние строки последовательности отличаются друг от друга ровно в одном символе.

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

Во входном файле содержится строка из символов 0 и 1

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

Выходной файл должен содержать 2^N строк — искомую последовательность.

Ограничения

1 ≤ N ≤ 15

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

1

1
0

110

110
111
101
100
000
001
011
010

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

Условие

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

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

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

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

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

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

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

Ограничения

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

2 1

QQ

3 5

QRR