// 4.4 Level order traversal

 #include <cstdio>

 #include <vector>

 using namespace std;

 struct TreeNode {

     int val;

     TreeNode *left;

     TreeNode *right;

     TreeNode(int _val = ): val(_val), left(nullptr), right(nullptr) {};

 };

 struct ListNode {

     int val;

     ListNode *next;

     ListNode(int _val = ): val(_val), next(nullptr) {};

 };

 void consructBSTFromSortedArray(vector<int> &v, int left, int right, TreeNode *&root)

 {

     if (left > right) {

         root = nullptr;

     } else {

         int mid = (left + right + ) / ;

         root = new TreeNode(v[mid]);

         consructBSTFromSortedArray(v, left, mid - , root->left);

         consructBSTFromSortedArray(v, mid + , right, root->right);

     }

 }

 void preorderTraversal(TreeNode *root, vector<ListNode *> &listHeads, vector<ListNode *> &listTails, int depth)

 {

     if (root == nullptr) {

         printf("# ");

     } else {

         while ((int)listHeads.size() < depth) {

             listHeads.push_back(nullptr);

             listTails.push_back(nullptr);

         }

         if (listHeads[depth - ] == nullptr) {

             listHeads[depth - ] = listTails[depth - ] = new ListNode(root->val);

         } else {

             listTails[depth - ]->next = new ListNode(root->val);

             listTails[depth - ] = listTails[depth - ]->next;

         }

         printf("%d ", root->val);

         preorderTraversal(root->left, listHeads, listTails, depth + );

         preorderTraversal(root->right, listHeads, listTails, depth + );

     }

 }

 void clearBinaryTree(TreeNode *&root)

 {

     if (root == nullptr) {

         return;

     } else {

         clearBinaryTree(root->left);

         clearBinaryTree(root->right);

         delete root;

         root = nullptr;

     }

 }

 void clearList(ListNode *&root)

 {

     ListNode *ptr;

     ptr = root;

     while (ptr != nullptr) {

         root = root->next;

         delete ptr;

         ptr = root;

     }

     root = nullptr;

 }

 int main()

 {

     TreeNode *root;

     int i, n;

     vector<int> v;

     vector<ListNode *> listHeads, listTails;

     ListNode *ptr;

     while (scanf("%d", &n) ==  && n > ) {

         for (i = ; i < n; ++i) {

             v.push_back(i + );

         }

         consructBSTFromSortedArray(v, , n - , root);

         preorderTraversal(root, listHeads, listTails, );

         printf("\n");

         for (i = ; i < (int)listHeads.size(); ++i) {

             printf("Level %d:", i + );

             ptr = listHeads[i];

             while (ptr != nullptr) {

                 printf(" %d", ptr->val);

                 ptr = ptr->next;

             }

             printf("\n");

             clearList(listHeads[i]);

         }

         v.clear();

         clearBinaryTree(root);

         listHeads.clear();

         listTails.clear();

     }

     return ;

 }