시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
4 초 | 512 MB | 2 | 1 | 1 | 100.000% |
A word $w$ is called bordered if there exists a word $u$, other then $w$ and empty word $\varepsilon$, such that $u$ is both suffix and prefix if $w$. For example, a word <<abbababb>> is bordered because <<abb>> is both its prefix and its suffix. A word that is not bordered is called borderless. For example, a word <<aabab>> is borderless.
Consider all borderless words of length $n$ composed of letters <<a>> and <<b>>. Let us denote the number of such words as $C_n$. Order them lexicographically --- by the first letter, then by the second one, etc, and number from 1 to $C_n$. Given $k$ find the $k$-th word in this order.
The input file contains multiple test cases.
Each test case contains two integers $n$ and $k$ on a line ($1 \le n \le 64$, $1 \le k \le C_n$).
Input is followed by a line with $n = k = 0$. There are at most 1000 test cases in one input file.
For each test case output one line --- the $k$-th lexicographically borderless word of length $n$.
5 1 5 2 5 3 5 4 5 5 0 0
aaaab aaabb aabab aabbb ababb