Skruç Dayının Qızılı

Dəyuşka Skruç bir çox qızıl külçə hazırlayıb və onları uzunluğu 2n - 2 olan sıfır və birlərdən ibarət ardıcıllıqlarla nömrələyib (hər bir külçənin nömrəsi onun üzərinə vurulub). Məlumdur ki,

1. İstənilən iki külçə fərqli nömrələrə malikdir.

2. Hər hansı bir külçənin nömrəsində ardıcıl iki sıfır yoxdur.

3. 2 xüsusiyyətinə cavab verən istənilən ardıcıllıq üçün, həmin nömrəyə malik külçə Dəyuşka Skruçun kolleksiyasında var.

Sonra Dəyuşka Skruç külçələri seyflərə yerləşdirməyə qərar verdi. Seyflərin kodları külçələrin nömrələri ilə oxşar şəkildə seçilib. Yəni

1. Seyfin kodu uzunluğu n - 2 olan sıfır və birlərdən ibarət ardıcıllıqdır.

2. İstənilən iki seyfin kodları fərqlidir.

3. Heç bir seyfin kodunda ardıcıl iki sıfır yoxdur.

4. 1 və 3 xüsusiyyətlərinə cavab verən istənilən kod üçün, həmin kodlu seyf Dəyuşka Skruçun anbarında var.

Dəyuşka Skruç hər bir seyfə eyni sayda qızıl külçə qoydu və qalan külçələri (seyflərin sayından az qalıb) xeyriyyəçiliyə göndərməyə qərar verdi. Hər bir seyfdə neçə külçə olduğunu tapın.

Giriş məlumatları

Tam ədəd n (3 ≤ n ≤ 70000).

Çıxış məlumatları

Hər bir seyfdə olan külçələrin sayını göstərin.