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

namespace ALDS1_8_A
{
    class Program
    {
        static void Main(string[] args)
        {
            string line;
            // int[] vals;

            //入力
            line = Console.ReadLine().Trim();
            var commandCount = int.Parse(line);

            var nodes = new Nodes<int>();

            for (int i = 0; i < commandCount; i++)
            {
                line = Console.ReadLine().Trim();
                var vals = line.Split(" ".ToCharArray(), StringSplitOptions.RemoveEmptyEntries).ToArray();
                if (vals[0] == "insert")
                {
                    nodes.Insert(int.Parse(vals[1]));
                }
                else
                {
                    Console.WriteLine(" " + String.Join(" ", nodes.Inorder().Select(x => x.Value).ToArray()));
                    Console.WriteLine(" " + String.Join(" ", nodes.Preorder().Select(x => x.Value).ToArray()));
                }

            }
        }
    }

    public class Nodes<T> where T : IComparable<T>
    {
        private Node Root { get; set; } = null;

        public void Insert(T val)
        {
            Node y = null; // x の親
            Node z = new Node() { Value = val };
            Node x = Root;
            while (x != null)
            {
                y = x;
                if (x.Value.CompareTo(z.Value) > 0) x = x.Left;
                else if (x.Value.CompareTo(z.Value) < 0) x = x.Right;
                else break;
            }
            z.Parent = y;
            if (y == null)
            {
                Root = z;
            }
            else if (z.Value.CompareTo(y.Value) < 0)
            {
                y.Left = z; // z を y の左の子にする
            }
            else
            {
                y.Right = z; // z を y の右の子にする
            }
        }

        public IEnumerable<Node> Preorder(Node node = null)
        {
            if (Root == null) 
                yield break;
            if (node == null)
                node = Root;

            yield return node;
            foreach (var child in node.Children())
            {
                foreach (var grandChild in Preorder(child))
                    yield return grandChild;
            }
        }

        public IEnumerable<Node> Inorder(Node node = null)
        {
            if (Root == null)
                yield break;
            if (node == null)
                node = Root;

            if (node.Left != null)
            {
                foreach (var grandChild in Inorder(node.Left))
                    yield return grandChild;
            }
            yield return node;
            if (node.Right != null)
            {
                foreach (var grandChild in Inorder(node.Right))
                    yield return grandChild;
            }
        }

        public IEnumerable<Node> Postorder(Node node = null)
        {
            if (Root == null)
                yield break;
            if (node == null)
                node = Root;

            foreach (var child in node.Children())
            {
                foreach (var grandChild in Postorder(child))
                    yield return grandChild;
            }
            yield return node;
        }

        public class Node
        {
            public T Value { get; set; }
            public Node Parent { get; set; }
            public Node Left { get; set; }
            public Node Right { get; set; }

            public string NodeType
            {
                get
                {
                    if (Parent == null)
                    {
                        return "root";
                    }
                    if (Left != null || Right != null)
                    {
                        return "internal node";
                    }
                    return "leaf";
                }
            }

            public int GetDepth()
            {
                if (Parent == null)
                {
                    return 0;
                }
                return Parent.GetDepth() + 1;
            }

            public IEnumerable<Node> Children()
            {
                if (Left != null) yield return Left;
                if (Right != null) yield return Right;
            }

            public override string ToString()
            {
                return $"node {Value}: parent = {(Parent != null ? Parent.Value.ToString() : "-1")}, {NodeType}";
            }
        }
    }
}



Measured memory_bytes: 118408