Код Грея
Коди Грея — це двійкова система нумерації, в якій два послідовні значення відрізняються лише одним бітом. Кожен N-бітовий код Грея складається з N бітів. Найпростіший випадок — це коли N = 1, де коди Грея є 0 і 1.
Розглянемо набір N-бітових кодів Грея. Щоб отримати N + 1-бітові коди Грея, можна скористатися простим методом. Спочатку запишіть наявні коди в стовпчик, проведіть лінію під останнім кодом, а потім "відобразіть" ці коди під лінією, тобто продублюйте список у зворотному порядку. Додайте 0 перед початковими кодами і 1 перед "відображеними". (Саме тому коди Грея також називають "відображеними бінарними кодами".)
Розглянемо приклад побудови кодів Грея для N = 2:
Список кодів Грея для N = 2 виглядає так: 00, 01, 11, 10.
Ось як можна згенерувати коди Грея для N = 3:
Ваше завдання — обчислити та вивести лише k-ий код N-бітових кодів Грея. Коди нумеруються з 0. Наприклад, якщо N = 3 і k = 4, програма повинна вивести 110.
Вхідні дані
Вхідні дані складаються з кількох тестів. Кожен тест — це один рядок, що містить значення N (1 ≤ N ≤ 72) і k (0 ≤ k ≤ 2^N−1). Останній рядок містить два нулі і не обробляється.
Зверніть увагу, що значення k може не вміщатися в 32 біт або навіть у 64 біт. Також важливо не обчислювати всі 2^N значення коду Грея, а зосередитися на обчисленні лише k-го значення.
Вихідні дані
Для кожного вхідного випадку виведіть номер випадку (1, 2, …), значення N і k, та k-те значення коду Грея (позначене як "g"). Дотримуйтесь формату, показаного в прикладах нижче.