Правительство Санкт-Битсбурга составляет техническое задание для украшения города к новому году.

Губернатор считает, что следует повесить на главной площади гирлянду из $$$n$$$ лампочек. Лампочки будут включаться и выключаться, и гирлянда будет радовать жителей города.

Главный дизайнер города решил, что гирлянда будет менять свой вид каждую секунду. Каждая лампочка, входящая в состав гирлянды, может быть включена или выключена. Дизайнер решил, что раз в секунду ровно одна из лампочек будет менять свое состояние: с включенной на выключенную или наоборот, с выключенной на включенную. При этом дизайнер хочет, чтобы комбинации включенных и выключенных лампочек повторялись с периодом $$$2^n$$$ секунд, причем за время периода в $$$2^n$$$ секунд все возможные $$$2^n$$$ комбинаций состояний лампочек были представлены на гирлянде.

Главный инженер города, однако, отметил, что постоянное включение и выключение лампочек приводит к их износу. Чтобы износ был равномерным, необходимо, чтобы все лампочки включались и выключались примерно одно и то же число раз.

Итоговое техническое задание для вас — главного программиста департамента информационных технологий правительства — выглядит так.

• Необходимо составить план из $$$2^n$$$ конфигураций лампочек $$$a_0, a_1, \ldots, a_{2^n-1}$$$, где $$$a_k$$$ — строка из $$$n$$$ нулей и единиц, $$$a_k[i]=1$$$ означает, что лампочка $$$i$$$ в конфигурации $$$a_k$$$ включена, а $$$a_k[i]=0$$$ означает, что лампочка $$$i$$$ в конфигурации $$$a_k$$$ выключена.
• Все конфигурации в плане должны быть различны.
• Этот план будет запущен по циклу, каждую секунду на гирлянде будет показываться очередная конфигурация, в $$$t$$$-ю секунду будет показываться конфигурация $$$a_{t \bmod 2^n}$$$.
• Соседние конфигурации должны отличаться состоянием ровно одной лампочки, аналогично конфигурации $$$a_{2^n-1}$$$ и $$$a_0$$$ также должны отличаться состоянием ровно одной лампочки.
• Обозначим как $$$c_i$$$ количество изменений состояния лампочки $$$i$$$ за время полного цикла, включая конечный переход от $$$a_{2^n-1}$$$ к $$$a_0$$$. Тогда для любых $$$i \ne j$$$ значения $$$c_i$$$ и $$$c_j$$$ должны различаться не более чем на $$$2$$$.

За работу!