//二叉树的层序遍历
#include<bits/stdc++.h>
using namespace std;
const int N=1000;
typedef struct BTNode{
    int val;
    struct BTNode *left;
    struct BTNode *right;
}*Bitree,BTNode;
void create(Bitree &t){
    int c;
    cin>>c;
    if(c==-1) t=NULL;
    else{
        t=new BTNode;
        t->val=c;
        create(t->left);
        create(t->right);
    }
}
            //       8
            //     3   10
            //  1    6    14
            //     4   7 13
           // 8 3 1 -1 -1 6 4 -1 -1 7 -1 -1 10 -1 14 13 -1 -1 -1
void preorder(Bitree t){
    if(t==NULL) return ;
    cout<<t->val<<" ";
    preorder(t->left);
    preorder(t->right);
}
vector<vector<int>>res;
void cen(Bitree t){
    queue<BTNode*>q;
    q.push(t);
    while(q.size()){
        int n=q.size();
        vector<int>ans;
        while(n--){
            auto t=q.front();
            ans.push_back(t->val);
            q.pop();
            if(t->left) q.push(t->left);
            if(t->right)q.push(t->right);
        }
        res.push_back(ans);
    }
}
vector<int>p;
void preorder1(Bitree t){
    stack<BTNode*>stk;
    while(!stk.empty()||t!=NULL){
        while(t){
            cout<<t->val<<" ";
            stk.push(t);
            p.push_back(t->val);
            t=t->left;
        }
        if(stk.size()){
            t=stk.top();//这里不能用auto t
            stk.pop();
            t=t->right;
        }
    }
}
int main(){
    Bitree t;
    create(t);
    preorder(t);
    cout<<endl;
    cen(t);
    for(auto xx:res){
       for(auto xx1:xx){
           cout<<xx1<<" ";
       }
       cout<<endl;
    }
    cout<<endl;
    preorder1(t);
    // for(auto xx2:p){
    //     cout<<xx2<<" ";
    // }

}