eolymp
bolt
Try our new interface for solving problems
Problems

Constructing BST

Constructing BST

Time limit 1 second
Memory limit 128 MiB

BST (Binary Search Tree) is an efficient data structure for searching. In a BST all the elements of the left sub-tree are smaller and those of right sub-tree are greater than the root. A typical example of BST is –

Normally, we construct BST by successively inserting an element. In that case, the ordering of elements has great impact on the structure of the tree. Look at the following cases:

In this problem, you have to find the order of 1 to n integers such that the BST constructed by them has height of at most h. The height of a BST is defined by the following relation:

  1. BST having no node has height 0.

  2. Otherwise, it equals to 1 plus maximum of the height of the left sub-tree and right sub-tree.

Again, several orderings can satisfy the criterion. In that case we prefer the sequence where smaller numbers come first. For example, for n = 4, h = 3 we want the sequence 1 3 2 4 rather than 2 1 4 3 or 3 2 1 4.

Input data

Each test case contains two positive integers n (1n10000) and h (1h30). Input is terminated by n = 0, h = 0. This case should not be processed. There can be at most 30 test cases.

Output data

Output of each test case should consist of a line starting with "Case #: " where "#" is the test case number. It should be followed by the sequence of n integers in the same line. There must not be any trailing space at the end of the line. If it is not possible to construct such tree then print "Impossible." (without the quotes).

Examples

Input example #1
4 3
4 1
6 3
0 0
Output example #1
Case 1: 1 3 2 4
Case 2: Impossible.
Case 3: 3 1 2 5 4 6