ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

1803. The Czechs' Rifles

Time limit: 3.0 second
Memory limit: 64 MB
The Czechoslovak Legion decided to stop the fierce fighting in Siberia and return home. However, it was not so easy to leave Russia, because they had too little money to pay for the sea voyage from Vladivostok to Europe. The Czechs decided to get the necessary amount of money by selling their rifles to the advancing Red troops. The total number of rifles they could sell was n. The first two rifles were ordinary, so the Czechs asked only one rouble for each of them. The ith rifle (i ≥ 3) costs as much as the (i−1)th and (i−2)th rifles together.
The bank notes that circulated in Russia at that time had nominal values equal to powers of an integer k (there were one-rouble, k-rouble, k2-rouble notes and so on). The Red troops had occupied enough printing plants for printing the necessary amount of notes. They paid for each rifle the exact amount of money the Czechs asked using the minimal possible quantity of notes.
When the Red Army got hold of the rifles, Chapaev asked Anka to order them according to the quantity of notes paid for each rifle. If the same quantity of notes was paid for two rifles, then the rifle with the smallest number should go first. Help Anka fulfill this request.


The only line contains the integers k and n separated with a space (2 ≤ k ≤ 10; 3 ≤ n ≤ 50000).


Output the permutation of the integers from 1 to n corresponding to the numbers of rifles in the required order.


10 8
1 2 3 4 8 7 5 6


After Anka fulfills Chapaev's request, the costs of the rifles in roubles will be {1, 1, 2, 3, 21, 13, 5, 8}.
Problem Author: Viktor Kamashev
Problem Source: NEERC 2010, Eastern subregional contest