GrayInc
Gray Inc. є виробником програмного забезпечення, що спеціалізується на управлінні кодами Грея. n-бінарний код, для n ≥ 1, є послідовністю слів w_0, w_1, ... яка включає всі можливі бінарні слова з n бітів. n-код Грея є n-бінарним кодом, в якому між будь-якими двома послідовними словами змінюється лише один біт, тобто вони відрізняються рівно в одній позиції. Як ви вже могли здогадатися, існує багато n-кодів Грея.
Gray Inc. виробляє свій власний особливий вид коду Грея наступним чином (назвемо G_n вироблений 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.