import java.util.*;
public class Main{
    static class Node
    {
        int data;
        Node left,right;
        Node(int val){
            data=val;
            left=null;
            right=null;
        }
    }
    static class Tree{
        Node create(int val){
            return new Node(val);
        }
        Node insert(Node root,int val)
        {
            if(root==null){
                return new Node(val);
            }
            if(val<root.data){
                root.left=insert(root.left,val);
            }
            else{
                root.right=insert(root.right,val);
            }
            return root;
        }
    }
    static void inorder(Node root)
    {
        if(root!=null){
            inorder(root.left);
            System.out.print(root.data+" ");
            inorder(root.right);
        }
    }
    static void preorder(Node root)
    {
        if(root!=null){
            System.out.print(root.data+" ");
            preorder(root.left);
            preorder(root.right);
        }
    }
    static void postorder(Node root)
    {
        if(root!=null){
            postorder(root.left);
            postorder(root.right);
            System.out.print(root.data+" ");
        }
    }
    public static void main(String[] args)
    {
        Scanner sc=new Scanner(System.in);
        Tree t=new Tree();
        int n=sc.nextInt();
        if(n<0 || n>10)
        {
            System.out.println("Invalid input");
            return;
        }
        Node root=null;
        for(int i=0;i<n;i++){
            if(!schasNextInt())
            {
                System.out.println("Invalid input");
            return;
            }
            int val=sc.nextInt();
            root=t.insert(root,val);
            if(val<0)
            {
                System.out.println("Invalid input");
            return;
            }
        }
        preorder(root);
        System.out.println();
        inorder(root);
        System.out.println();
        postorder(root);
    }
}