#include <iostream>
using namespace std;
struct TreeNode{
    int data;
    TreeNode* left;
    TreeNode* right;
};
TreeNode* build(TreeNode* root,int x){
    if(root==NULL){
        root=(TreeNode*)malloc(sizeof(TreeNode));
        root->data=x;
    }
    else if(x<root->data) root->left=build(root->left,x);
    else if(x>root->data) root->right=build(root->right,x);
    return root;
}
void PreOrder(TreeNode* root){
    if(root==NULL) return;
    cout<<root->data<<" ";
    PreOrder(root->left);
    PreOrder(root->right);
}
void InOrder(TreeNode* root){
    if(root==NULL) return; 
    InOrder(root->left);
    cout<<root->data<<" ";
    InOrder(root->right);
}
void PostOrder(TreeNode* root){
    if(root==NULL) return;
    PostOrder(root->left);
    PostOrder(root->right);
    cout<<root->data<<" ";
}
int main() {
   int n,x;
   while(scanf("%d",&n)!=EOF){
     TreeNode* root=NULL;
     for(int i=0;i<n;i++){
        cin>>x;
        root=build(root,x);
     }
     PreOrder(root);
     printf("\n");
     InOrder(root);
     printf("\n");
     PostOrder(root);
     printf("\n");
   }
   return 0;
}
// 64 位输出请用 printf("%lld")