using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace _20170410_AOJ_ALDS1_8A
{
    class ALDS1_8A
    {
        static void Main(string[] args)
        {
            for (;;)
            {
                string line = Console.ReadLine();
                if (string.IsNullOrEmpty(line))
                {
                    break;
                }

                BinaryTree bt = new BinaryTree();
                int n = int.Parse(line);
                for(int i=0;i<n;i++)
                {
                    string[] command = Console.ReadLine().Split(' ');
                    switch(command[0])
                    {
                        case "insert":
                            int key = int.Parse(command[1]);
                            bt.Insert(key);
                            break;
                        case "print":
                            Console.Write(" ");
                            Console.WriteLine(string.Join(" ", bt.InOrder().Select(x => x.Key.ToString()).ToArray()));
                            Console.Write(" ");
                            Console.WriteLine(string.Join(" ", bt.PreOrder().Select(x => x.Key.ToString()).ToArray()));
                            break;
                    }
                }
            }
        }
    }

    class BinaryTree
    {
        List<TreeNode> list;
        public TreeNode Root { get { return GetRoot(); } }
        public BinaryTree()
        {
            list = new List<TreeNode>();
        }

        private TreeNode GetRoot()
        {
            if (list.Count == 0) return null;

            TreeNode temp = list[0];
            while (temp.Parent != null)
            {
                temp = temp.Parent;
            }

            return temp;
        }

        public void Insert(int z)
        {
            TreeNode tn = new TreeNode();
            tn.Key = z;
            Insert(tn);
        }

        public void Insert(TreeNode z)
        {
            TreeNode y = null;
            TreeNode x = Root;
            
            while(x!=null)
            {
                y = x;
                x = (z.Key < x.Key) ? x.Left : x.Right;
            }

            z.Parent = y;

            list.Add(z);
            if(y==null)
            {
            }
            else if(z.Key < y.Key)
            {
                y.Left = z;
                z.Parent = y;
            }
            else
            {
                y.Right = z;
                z.Parent = y;
            }
        }

        public TreeNode[] PreOrder()
        {
            List<TreeNode> list = new List<TreeNode>();
            PreOrder(list, Root);
            return list.ToArray();
        }

        static void PreOrder(List<TreeNode> list, TreeNode tn)
        {
            list.Add(tn);

            if (tn.Left != null)
            {
                PreOrder(list, tn.Left);
            }

            if (tn.Right != null)
            {
                PreOrder(list, tn.Right);
            }
        }

        public TreeNode[] InOrder()
        {
            List<TreeNode> list = new List<TreeNode>();
            InOrder(list, Root);
            return list.ToArray();
        }

        static void InOrder(List<TreeNode> list, TreeNode tn)
        {
            if (tn.Left != null)
            {
                InOrder(list, tn.Left);
            }

            list.Add(tn);

            if (tn.Right != null)
            {
                InOrder(list, tn.Right);
            }
        }

        static void PostOrder(List<TreeNode> list, TreeNode tn)
        {
            if (tn.Left != null)
            {
                PostOrder(list, tn.Left);
            }

            if (tn.Right != null)
            {
                PostOrder(list, tn.Right);
            }

            list.Add(tn);
        }
    }

    class TreeNode
    {
        public int Key { get; set; }
        public TreeNode Parent { get; set; }
        public TreeNode Left { get; set; }
        public TreeNode Right { get; set; }
        public TreeNode()
        {
        }
    }
}



Measured memory_bytes: 83088