O. Код Грея

Выведите все $2^N$ строк длины $N$ из нулей и единиц так, чтобы любые две соседние в выводе строки отличались ровно в одной позиции. Первой должна идти строка из одних нулей.

Такой порядок называется кодом Грея. Он существует при любом $N$ и строится рекурсивно: возьмите код Грея длины $N-1$, припишите ко всем строкам ноль, затем выпишите тот же код в обратном порядке с единицей впереди.

Ответ единственный, если дополнительно потребовать, чтобы вторая строка отличалась от первой в последней позиции. Это условие и имеется в виду.

Одна строка содержит число $N$ ($1 \le N \le 15$).

Все $2^N$ строк, по одной на строку, в порядке кода Грея.