Foul Play

Avropa futbol turnirində n iştirakçı komanda var. Birinci turda, hər bir komanda başqa bir komandaya qarşı oynayacaq şəkildə n/2 oyun keçirilir. Hər turdan sonra yalnız qalib komandalar növbəti tura keçirlər. İkinci turda, hər bir birinci tur qalibi başqa bir birinci tur qalibinə qarşı oynayacaq şəkildə n/4 oyun keçirilir. Nəticədə, yalnız iki komanda final oyunu oynamaq üçün qalır. Final oyununun qalibi turnirin çempionu olur.

Hollandiya futbol komandası bəlkə də dünyanın ən yaxşı komandası deyil. Lakin, onlar hələ də kifayət qədər yaxşı komandadır. Onlar asanlıqla digər komandaların ən azı yarısını məğlub edə bilərlər. Üstəlik, Hollandiya komandasının birbaşa qarşılaşmada məğlub edə bilmədiyi hər bir komanda t üçün, t-ni məğlub edən, lakin Hollandiya komandasına məğlub olan başqa bir komanda t' var.

Hollandiya məşqçisi turniri elə manipulyasiya etmək istəyir ki, Hollandiya komandası çempion olsun. O, hər bir komanda cütü üçün, əgər onlar arasında oyun keçirilsəydi, hansı komandanın mütləq qalib gələcəyini bilir.

Problem

Hər iki komanda üçün, əgər onlar bir-birinə qarşı oynasaydılar, hansının qalib gələcəyini əvvəlcədən bilirsiniz. (Bu, nokaut turniri olduğundan, heç-heçə olmayacaq.) Üstəlik, sevimli komandanızın digər komandaların ən azı yarısını məğlub edə biləcəyini və sevimli komandanızın məğlub edə bilmədiyi hər bir komanda t üçün, t-ni məğlub edən, lakin özünün sevimli komandanız tərəfindən məğlub edilən bir komanda t' olduğunu dəqiq bilirsiniz.

Sevimli komandanızın turniri qazanmasını təmin edəcək bir turnir cədvəli müəyyən edin.

Giriş verilənləri

Hər bir test üçün, giriş aşağıdakı kimidir:

• Komandaların sayını göstərən bir sətir n, burada n iki qüvvətidir və 2 ≤ n ≤ 1024. Komandalar 1-dən n-ə qədər nömrələnmişdir, burada 1 sizin sevimli komandanızdır.

• n sətir, hər biri n ikilik rəqəmdən ibarət bir sətir. k-cı rəqəm j-ci sətirdə əgər j komandası k komandasını mütləq məğlub edərsə '1', əks halda '0' olur. Bir komanda özünə qarşı oynaya bilməz, buna görə də j-ci sətirdə j-ci rəqəm '0' olur. Əgər j ≠ k, k-cı rəqəm j-ci sətirdə j-ci rəqəmdən k-cı sətirdə fərqlidir.

Çıxış verilənləri

Hər bir test üçün, n-1 sətir çıxış verin, komanda 1-in turniri qazanmasını təmin edən bir turnir cədvəlini göstərir.

İlk n/2 sətir turnirin birinci turunu təsvir edir. Növbəti n/4 sətir ikinci turu təsvir edir, əgər varsa, və s. Son sətir final oyununu təsvir edir.

Hər sətir iki tam ədəd x və y ehtiva edir, bu da komanda x-in komanda y-ə qarşı oyun oynadığını göstərir.

Əgər komanda 1-in qalib gəldiyi bir neçə turnir cədvəli varsa, bu turnir cədvəllərindən hər hansı biri düzgün cavab kimi qəbul ediləcək.