Gwen's Gift

문제

Gwen loves most numbers. In fact, she loves every number that is not a multiple of $nn$ (she really hates the number $nn$). For her friends' birthdays this year, Gwen has decided to draw each of them a sequence of $n-1n-1$ flowers. Each of the flowers will contain between $11$ and $n-1n-1$ flower petals (inclusive). Because of her hatred of multiples of $nn$, the total number of petals in any non-empty contiguous subsequence of flowers cannot be a multiple of $nn$. For example, if $n=5n\; =\; 5$, then the top two paintings are valid, while the bottom painting is not valid since the second, third and fourth flowers have a total of $1010$ petals. (The top two images are Sample Input $33$ and $44$.)

Gwen wants her paintings to be unique, so no two paintings will have the same sequence of flowers.  To keep track of this, Gwen recorded each painting as a sequence of $n-1n-1$ numbers specifying the number of petals in each flower from left to right.  She has written down all valid sequences of length $n-1n-1$ in lexicographical order. A sequence $a_1,a_2,\dots ,a_{n-1}a\_1,a\_2,\backslash dots,\; a\_\{n-1\}$ is lexicographically smaller than $b_1,b_2,\dots ,b_{n-1}b\_1,\; b\_2,\; \backslash dots,\; b\_\{n-1\}$ if there exists an index $kk$ such that $a_i=b_{i}a\_i\; =\; b\_i$ for and .

What is the $kk$th sequence on Gwen's list?

입력

The input consists of a single line containing two integers $nn$ ($2\le n\le 10002\; \backslash leq\; n\; \backslash leq\; 1\backslash ,000$), which is Gwen's hated number, and $kk$ ($1\le k\le {10}^{18}1\; \backslash leq\; k\; \backslash leq\; 10^\{18\}$), which is the index of the valid sequence in question if all valid sequences were ordered lexicographically. It is guaranteed that there exist at least $kk$ valid sequences for this value of $nn$.

출력

Display the $kk$th sequence on Gwen's list.