Considerăm şirurile de N biţi cu proprietatea că bitul de pe orice poziţie pară este mai mare sau egal cu biţii alăturaţi acestuia (adică, bitul de pe poziţia 2i este mai mare sau egal decât biţii de pe poziţiile 2i-1 şi 2i+1, evident dacă aceste poziţii există). De exemplu, 01110 sau 01011 îndeplinesc această proprietate, pe când şirul 11100 nu o îndeplineşte pentru că al patrulea bit este mai mic decât vecinul său de pe poziţia a treia. Toate şirurile de N biţi care îndeplinesc această condiţie le ordonăm lexicografic şi numerotăm aceste şiruri începând cu 1.
Cerinţă
Scrieţi un program care citeşte două numere naturale N şi K şi determină şirul de N biţi cu proprietatea cerută, al K-lea din punct de vedere lexicografic.
Date de intrare
Fişierul de intrare parbit.in
conţine pe prima linie un număr natural N reprezentând lungimea şirurilor. Pe linia a doua se află numărul natural K.
Date de ieşire
Fişierul de ieşire parbit.out
va conţine o singură linie pe care veţi scrie al K-lea şir (din punct de vedere lexicografic) de N biţi care îndeplineşte condiţia că bitul de pe orice poziţie pară este mai mare sau egal cu biţii alăturaţi acestuia.
Biţii şirului soluţie vor fi scrişi fără spaţii.
Restricţii
1 <= N <= 450
Numărul natural K are mai puţin de 100 de cifre şi este cuprins între 1 şi numărul maxim posibil de şiruri de N biţi care îndeplinesc condiţia cerută.
Exemplu
parbit.in
parbit.out
Explicaţie
3
4
110
Şirurile de 3 biţi (ordonate lexicografic) care îndeplinesc condiţia sunt: 000, 010, 011, 110, 111. Al patrulea şir este deci 110