Dina loves most numbers. In fact, she loves every number that is not a multiple of n (she really hates the number n). For her friends’ birthdays this year, Dina has decided to draw each of them a sequence of n−1 flowers. Each of the flowers will contain between 1 and n−1 flower petals (inclusive). Because of her hatred of multiples of n, the total number of petals in any non-empty contiguous subsequence of flowers cannot be a multiple of n. For example, if n=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 10 petals. (The top two images are Sample Input 3 and 4.)
Dina wants her paintings to be unique, so no two paintings will have the same sequence of flowers. To keep track of this, Dina recorded each painting as a sequence of n−1 numbers specifying the number of petals in each flower from left to right. She has written down all valid sequences of length n−1 in lexicographical order. A sequence a1,a2,…,a(n−1) is lexicographically smaller than b1,b2,…,bn−1 if there exists an index k such that ai=bi for i < k and ak < bk.
What is the kth sequence on Dina’s list?
Input The input consists of a single line containing two integers n (2≤n≤1000), which is Dina’s hated number, and k (1≤k≤1018), 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 k valid sequences for this value of n.
Output Display the kth sequence on Dina’s list.
Sample Input 1 4 3 Sample Output 1 2 1 2
Sample Input 2 2 1 Sample Output 2 1
Sample Input 3 5 22 Sample Output 3 4 3 4 2
Sample Input 4 5 16 Sample Output 4 3 3 3 3