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

namespace ALDS1_8_A
{
    class Program
    {
 
        static void Main(string[] args)
        {
            NodeItem BaseItem = null;

            // ??????????????\???????????????????????\????????°??¨??????
            int iInputNum = int.Parse(Console.ReadLine());

            // ??\???????????¨??\?????????????????¨??????????????????
            for (int i = 0; i < iInputNum; i++)
            {
                // ??\??????????????????
                string[] str_List = Console.ReadLine().Split(' ');


                // ???????????£????????????????????????
                if (str_List[0] == "insert")
                {
                    insert(ref BaseItem, int.Parse(str_List[1]));
                }
                // print ??¨????????\??????
                else
                {
                    BaseItem.write_InorderTree();
                    Console.WriteLine();
                    BaseItem.write_PreorderTree();
                    Console.WriteLine();
                }
            }
        }

        // insert??????
        static void insert(ref NodeItem tree, int key)
        {
            NodeItem x = tree;
            NodeItem y = null;
            NodeItem z = new NodeItem(key);

            while (x != null)
            {
                y = x;
                if (z.key < y.key)
                {
                    x = x.left;
                }
                else
                {
                    x = x.right;
                }
            }
            z.section = y;
            if (y == null)
            {
                tree = z;
            }
            else if (z.key < y.key)
            {
                y.left = z;
            }
            else
            {
                y.right = z;
            }
        }
    }


    // ??????????????¨????????????????§????
    class NodeItem
    {
        public int key;
        public NodeItem section;    // ???
        public NodeItem left;       // ???
        public NodeItem right;      // ???

        public NodeItem(int key)
        {
            this.key = key;
        }

        // ???????????????????????§??¨????????????
        public void write_InorderTree()
        {
            // ???????????????????????¨????????´?????????????????????????????????????????????
            if (left != null)
            {
                left.write_InorderTree();
            }
            Console.Write(" ");
            Console.Write(key); // ????????????
            // ???????????????????????¨????????´?????????????????????????????????????????????
            if (right != null)
            {
                right.write_InorderTree();
            }
        }
        // ???????????????????????§??¨????????????
        public void write_PreorderTree()
        {
            Console.Write(" ");
            Console.Write(key); // ????????????
            // ???????????????????????¨????????´?????????????????????????????????????????????
            if (left != null)
            {
                left.write_PreorderTree();
            }
            // ???????????????????????¨????????´?????????????????????????????????????????????
            if (right != null)
            {
                right.write_PreorderTree();
            }
        }
    }
}

Measured memory_bytes: 46268