Задача D. Код Грея ≡

Условие

Дана строка, состоящая из N символов 0 и 1. Требуется построить последовательность из всех возможных строк длиной N, состоящих из 0 и 1, такую что:

• первая строка последовательности — входная строка;
• каждая строка входит в последовательность один раз;
• соседние строки последовательности отличаются друг от друга ровно в одном символе.

Формат входного файла

Во входном файле содержится строка из символов 0 и 1

Формат выходного файла

Выходной файл должен содержать 2^N строк — искомую последовательность.

Ограничения

1 ≤ N ≤ 15

Примеры тестов

1

1
0

110

110
111
101
100
000
001
011
010