#include<iostream>
#include<queue>
using namespace std;
class node{
public:
    node *left;
    node *right;
    int data;
    node(int d)
    {
        data = d;
        left = NULL;
        right = NULL;
    }
};

node *buildTree(){
    int d;
    cin>>d;
    if(d == -1){
        return NULL;
    }
    node *root = new node(d);
    root->left = buildTree();
    root->right = buildTree();
    return root;
}
void print_pre(node *root){
    if(root == NULL){
        return;
    }
    cout<<root->data<<" ";
    print_pre(root->left);
    print_pre(root->right);
}
void print_in(node *root){
    if(root == NULL){
        return;
    }
    print_in(root->left);
    cout<<root->data<<" ";
    print_in(root->right);
}
void print_post(node *root){
    if(root == NULL){
        return;
    }
    print_post(root->left);
    print_post(root->right);
    cout<<root->data<<" ";
}
int height(node *root){
    if(root==NULL){
        return 0;
    }
    int lh = height(root->left);
    int rh = height(root->right);
    return max(lh,rh)+1;
}
void Printkthlevel(node *root ,int k){
    if(root==NULL){
        return;
    }
    if(k==1){
        cout<<root->data<<" ";
        return;
    }
    Printkthlevel(root->left,k-1);
    Printkthlevel(root->right,k-1);
}
void printAllLevels(node *root){
    int h = height(root);
    for(int i=1;i<=h;i++){
        Printkthlevel(root,i);
         cout<<endl;
    }
    return;
}
void bfs(node *root){
    queue<node*>q;
    q.push(root);
    //for printing each level in next line
    q.push(NULL);
    while(!q.empty()){
        node *f = q.front();

        //for printing each level in next line
        if(f==NULL){
            cout<<endl;
            q.pop();
            if(!q.empty()){
                q.push(NULL);
            }
        }
        else{
            cout<<f->data<<" ";
            q.pop();
            if(f->left){
                q.push(f->left);
            }
            if(f->right){
                q.push(f->right);
            }
        }

    }
    return;
}
int Count(node*root){
    if(root == NULL){
        return 0;
    }
    return 1+Count(root->left)+Count(root->right);
}
int sumAllNodes(node *root){
    int sum=0;
    if (root==NULL){
        return 0;
    }
    sum += (root->data+sumAllNodes(root->left)+sumAllNodes(root->right));
    return sum;

}
int diameter(node *root){
    if(root == NULL){
        return 0;
    }
    int h1 = height(root->left);
    int h2 = height(root->right);
    int case1 = h1+h2;
    int case2 = diameter(root->left);
    int case3 = diameter(root->right);
    return max(case1,max(case2,case3));
}
class Pair {
public:
    int height;
    int diameter;
};
Pair diameterEfficient(node *root){
    //p.first = height, p.second = diameter
    Pair p,left,right;

    if(root==NULL){
        p.height = p.diameter = 0;
        return p;
    }
    left = diameterEfficient(root->left);
    right = diameterEfficient(root->right);
    p.height = 1+ max(left.height,right.height);
    p.diameter = max(left.height+right.height,max(left.diameter,right.diameter));
    return p;
}
int replaceSum(node *root){
    if(root == NULL){
        return 0;
    }
    if(root->left==NULL||root->right==NULL){
        return root->data;
    }
    int leftSum = replaceSum(root->left);
    int rightSum = replaceSum(root->right);

    int temp = root->data;
    root->data = leftSum+rightSum;
    return temp+root->data;

}
int main(){
    node *root = buildTree();
   
    bfs(root);
   cout<<endl;
     replaceSum(root);
     bfs(root);
return 0;}