Description
Niflheimr loves playing with trees, and this time he wants to try trees with multiple children.
So he begins with the simplest part: traversing the tree.
Given the height of the tree and the number of children for each node (except for leaf nodes), and number(編號) the tree nodes from top to bottom, from left to right. Id begins with 0.
Niflheimr wants to perform a preorder-like traversal. That is, for every tree node, print out the id of itself first, then traverse its children from left to right.
For example, height = 3 and number of children = 3,
The number inside the nodes are their ids.
The preorder-like traversal sequence will be "0 1 4 5 6 2 7 8 9 3 10 11 12".
Input
Input contains a single line with two integers.
The first integer is the height of the tree.
The second integer is the number of childs for an internal node.
It is guaranteed that:
- The height of the tree won't exceed 20.
- The number of children for each node (except for leaf nodes) is less than 5.
- The number of total nodes in the tree won't exceed 5*106 (Is it necessary to build the whole tree?)
Output
Print out the preorder-like traversal sequence of the tree. There is a space after each number, and print a '\n' at the end of the output.