GrayInc
Gray Inc. — это компания, занимающаяся разработкой программного обеспечения, которая специализируется на управлении кодами Грея. n-битный код, где n ≥ 1, представляет собой последовательность слов w_0, w_1, ... включающую все возможные двоичные слова длиной n бит. n-код Грея — это n-битный код, в котором любые два последовательных слова отличаются ровно в одной позиции, то есть изменяется только один бит. Как вы, возможно, знаете, существует множество различных n-кодов Грея.
Gray Inc. создает свой собственный вариант кода Грея следующим образом (назовем его G_n, где n ≥ 1):
Обозначения, используемые для определения G_n, имеют следующий смысл:
bA : добавляет бит b к каждому элементу последовательности A;
AB : объединяет последовательности A и B;
A^R : последовательность, в которой элементы последовательности A расположены в обратном порядке.
Например,
и
Обратите внимание, что G_n является не только n-кодом Грея, но и циклическим кодом Грея, поскольку первое слово в последовательности можно рассматривать как следующее за последним в последовательности.
Gray Inc. хочет, чтобы вы помогли решить следующую задачу: дано двоичное слово w в G_n и натуральное число m, они хотят получить двоичное слово в последовательности G_n, которое находится на m позиций вперед от w в списке (учитывая описанный выше циклический порядок). Можете ли вы им помочь?
Входные данные
Входные данные состоят из нескольких случаев, каждый из которых задается строкой с целым числом m (0 < m ≤ 1000) и двоичным n-словом w (1 ≤ n ≤ 100), разделенных пробелом.
Конец ввода обозначается строкой с m = 0 и w = 0.
Выходные данные
Для каждого входного случая ваше решение должно выводить n-битное слово, которое находится на m позиций вперед от w в списке G_n.