Код Грея — це список усіх ~2^n~ бітових рядків довжини ~n~, де будь-які два послідовні рядки відрізняються рівно одним бітом (тобто їх відстань Хеммінга дорівнює одиниці).

Ваше завдання — створити код Грея для заданої довжини ~n~.

Обмеження

• ~1 \le n \le 16~

Формат вхідних даних

Єдиний вхідний рядок містить ціле число ~n~.

Формат вихідних даних

Надрукуйте ~2^n~ рядків, які описують код Грея. Ви можете роздрукувати будь-яке дійсне рішення.

Приклад вхідних даних

2

Приклад вихідних даних

00
01
11
10