#include <bits/stdc++.h>
using namespace std;
struct TreeNode{
	TreeNode* left;
	TreeNode* right;
	int data;
	TreeNode(int val):data(val),left(nullptr),right(nullptr){}
};
 vector<vector<int> > treeTraversal(TreeNode* root) {
 	vector<int>pre,post,in;
	if(root == nullptr)return {in,pre,post};
	
 	stack<pair<TreeNode*,int>>st;
 	st.push({root,1});
 	
 	while(!st.empty()){
 	TreeNode* one;
int two;
 	tie(one,two) = st.top();
 		st.pop();
 	
 		if(two == 1){
 			st.push({one,2});
 			pre.push_back(one->data);
 		    if(one->left){
 		    	st.push({one->left,1});
 		    }
 		}else if(two == 2){
 			st.push({one,3});
 			in.push_back(one->data);
 			if(one->right){
 				st.push({one->right,1});
 			}
 		}else{
 			post.push_back(one->data);
 		}
 	}
 	return {in,pre,post};
 }
 TreeNode* buildTree(){
 	int x;cin>>x;
 	if(x == -1)return nullptr;
 	
 	TreeNode* root = new TreeNode(x);
 	
 	queue<TreeNode*>q;
 	q.push(root);
 	while(!q.empty()){
 	 	TreeNode*node =q.front();q.pop();
 	 	cin>>x;
 	 	if(x!=-1){
 	 		node->left = new TreeNode(x);
 	 		q.push(node->left);
 	 	}
 	 	cin>>x;
 	 	if(x!=-1){
 	 		node->right = new TreeNode(x);
 	 		q.push(node->right);
 	 	}
 	}
 	return root;
 }
int main() {
	TreeNode* root = buildTree();
   /** TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    **/
    vector<vector<int>>ans = treeTraversal(root);
    for(int val : ans[0])cout<<val<<" ";
    cout<<endl;
    cout<<"in"<<endl;
    for(int val : ans[1])cout<<val<<" ";
    cout<<endl;
    cout<<"post"<<endl;
    for(int val : ans[2])cout<<val<<" ";
    cout<<endl;
   
	return 0;
}