Constructing BST#1516
BST (Binary Search Tree) is an efficient data structure for searching. In a BST, all elements of the left subtree are less than the root value, and all elements of the right subtree are greater. Consider the following example:
Usually, a BST is constructed by successively inserting elements. In this case, the order in which elements are inserted affects the structure of the resulting tree. For example:
In this problem, you are to find an order of inserting the integers from to such that the resulting BST has height not greater than . The height of a BST is defined as follows:
A BST with no nodes has height .
Otherwise, its height is plus the maximum of the heights of the left and right subtrees.
There can be several insertion orders that meet the requirements. In this case, output the sequence where smaller numbers come first. For example, for n = 4, h = 3, output the sequence , not or .
Each test consists of two positive integers (1 \leq n \leq 10000) and (1 \leq h \leq 30). The input terminates with n = 0, h = 0, which should not be processed. There are at most test cases.
Output the result for each test case on a separate line. Each line should start with "Case #: ", where # is the test case number. Then, on the same line, output the sequence of integers—the order in which the nodes should be inserted into a BST of height not greater than . No extra spaces should appear at the end of a line. If it is impossible to construct such a tree, output Impossible.
Example 1