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

/*
 */

public class ALDS1_8_A
{
    private struct Node
    {
        public int NodeId;
        public int Value;
        public int ParentId;
        public int LeftId;
        public int RightId;

        public Node(int nodeId)
        {
            NodeId = nodeId;
            Value = 0;
            ParentId = -1;
            LeftId = -1;
            RightId = -1;
        }
    }

    public static void Main(string[] args)
    {
        //var exStdIn = new System.IO.StreamReader( "input.txt" );
        //System.Console.SetIn( exStdIn );

        int n = int.Parse(Console.ReadLine());
        Node[] nodes = new Node[n];
        for (int i = 0; i < n - 1; i++)
        {
            nodes[i] = new Node(i);
        }

        for (int i = 0; i < n; i++)
        {
            string[] str = Console.ReadLine().Split(' ');
            if (str[0] == "insert")
            {
                Insert(nodes, i, int.Parse(str[1]));
            }
            else if (str[0] == "print")
            {
                int rootId = -1;
                for (int j = 0; j < n; j++)
                {
                    if (nodes[j].ParentId == -1)
                    {
                        rootId = j;
                        break;
                    }
                }
                StringBuilder sb = new StringBuilder();
                Inorder(nodes, sb, rootId);
                sb.AppendLine();
                Preorder(nodes, sb, rootId);
                Console.WriteLine(sb.ToString());
            }
        }
    }

    private static void Insert(Node[] nodes, int index, int value)
    {
        int parent = 0;
        nodes[index].Value = value;
        if (index == 0)
        {
            return;
        }
        while (true)
        {
            Node parentNode = nodes[parent];
            if (value < parentNode.Value)
            {
                if (parentNode.LeftId != -1)
                {
                    parent = parentNode.LeftId;
                }
                else
                {
                    nodes[parent].LeftId = index;
                    nodes[index].ParentId = parent;
                    return;
                }
            }
            else
            {
                if (parentNode.RightId != -1)
                {
                    parent = parentNode.RightId;
                }
                else
                {
                    nodes[parent].RightId = index;
                    nodes[index].ParentId = parent;
                    return;
                }
            }
        }
    }

    private static void Preorder(Node[] nodes, StringBuilder sb, int index)
    {
        sb.AppendFormat(" {0}", nodes[index].Value.ToString());
        if (nodes[index].LeftId != -1)
        {
            Preorder(nodes, sb, nodes[index].LeftId);
        }
        if (nodes[index].RightId != -1)
        {
            Preorder(nodes, sb, nodes[index].RightId);
        }
    }

    private static void Inorder(Node[] nodes, StringBuilder sb, int index)
    {
        if (nodes[index].LeftId != -1)
        {
            Inorder(nodes, sb, nodes[index].LeftId);
        }
        sb.AppendFormat(" {0}", nodes[index].Value.ToString());
        if (nodes[index].RightId != -1)
        {
            Inorder(nodes, sb, nodes[index].RightId);
        }
    }

    private static void Postorder(Node[] nodes, StringBuilder sb, int index)
    {
        if (nodes[index].LeftId != -1)
        {
            Postorder(nodes, sb, nodes[index].LeftId);
        }
        if (nodes[index].RightId != -1)
        {
            Postorder(nodes, sb, nodes[index].RightId);
        }
        sb.AppendFormat(" {0}", nodes[index].Value.ToString());
    }
}



Measured memory_bytes: 69468