#include <cassert>
#include <iostream>
#include <sstream>
#include <vector>
#include <list>
#include <algorithm>
 
enum TNodeType {ntRoot, ntInternal, ntLeaf};
template<typename T>
class TTree;
 
template<typename T>
class TNode
{
    const T FValue;
    TNode* FParent;
    TNode* FLeft;
    TNode* FRight;

public:
    TNode(const T& Value)
     : FValue(Value)
    {
        FParent = NULL;
        FLeft   = NULL;
        FRight  = NULL;
    }
    T Value()const
    {
        return FValue;
    }
    void AddNode(TNode* Node)
    {
        Node->FParent = this;
        if(FValue < Node->FValue){
            assert(FRight);
            FRight = Node;
        }else{
            assert(FLeft);
            FLeft  = Node;
        }
    }
    void SetLeft(TNode* Node)
    {
        Node->FParent = this;
        FLeft = Node;
    }
    void SetRight(TNode* Node)
    {
        Node->FParent = this;
        FRight = Node;
    }
    void SetParent(TNode* Node)
    {
        FParent = Node;
    }
    TNode* CreateLeft(const T& Value)
    {
        assert(FLeft == NULL);
        SetLeft(new TNode(Value));
        return FLeft;
    }
    TNode* CreateRight(const T& Value)
    {
        assert(FRight == NULL);
        SetRight(new TNode(Value));
        return FRight;
    }
    const TNode* Parent()const
    {
        return FParent;
    }
    const TNode* Left()const
    {
        return FLeft;
    }
    TNode* Left()
    {
        return FLeft;
    }
    const TNode* Right()const
    {
        return FRight;
    }
    TNode* Right()
    {
        return FRight;
    }
    const TNode* Find(const T& Value)const
    {
        // std::cout << "Find(" << Value << ")" << std::endl;
        if(FValue == Value) return this;
        TNode* Node = FValue < Value ? FRight : FLeft;
        if(Node) return Node->Find(Value);
        return NULL;
    }
    TNode* Find(const T& Value)
    {
        return const_cast<TNode*>(const_cast<const TNode*>(this)->Find(Value));
    }
};

template<typename T>
int GetNodeDepth(const TNode<T>* Node)
{
    assert(Node);
    int Depth = 0;
    while(Node->Parent()){
        Node = Node->Parent();
        Depth++;
    }
    return Depth;
}
 
template<typename T>
TNodeType GetNodeType(const TNode<T>* Node)
{
    assert(Node);
    if(Node->Parent() == NULL) return ntRoot;
    if(Node->Left() || Node->Right()) return ntInternal;
    return ntLeaf;
}
std::string GetNodeTypeText(const TNodeType& Type)
{
    switch(Type){
    case ntRoot:     return "root";
    case ntInternal: return "internal node";
    case ntLeaf:     return "leaf";
    }
    assert(false);
    return "";
}
 
template<typename T>
const TNode<T>* GetSibling(const TNode<T>* Node)
{
    assert(Node);
    const TNode<T>* Parent = Node->Parent();
    if(Parent == NULL) return NULL;
    if(Parent->Left()  && Parent->Left()  != Node) return Parent->Left();
    if(Parent->Right() && Parent->Right() != Node) return Parent->Right();
    return NULL;
}
template<typename T>
const TNode<T>* GetRoot(const TNode<T>* Node)
{
    if(Node->Parent()) return GetRoot(Node->Parent());
    return Node;
}
template<typename T>
int GetDegree(const TNode<T>* Node)
{
    return (Node->Left() ? 1 : 0) + (Node->Right() ? 1 : 0);
}

template<typename T>
int GetHeight(const TNode<T>* Node)
{
    if(Node == NULL) return -1;
    return 1 + std::max(GetHeight(Node->Left()), GetHeight(Node->Right()));
}
template<typename T>
void PrintNode(const TNode<T>* Node)
{
    assert(Node);
// node 0: parent = -1, sibling = -1, degree = 2, depth = 0, height = 3, root    
    std::cout << 
    "node "       << Node->Value() <<
    ": parent = " << (Node->Parent() ? Node->Parent()->Value() : -1) <<
    ", sibling = "<< (GetSibling(Node) ? GetSibling(Node)->Value() : -1) <<
    ", degree = " << GetDegree(Node) <<
    ", depth = "  << GetNodeDepth(Node) <<
    ", height = "  << GetHeight(Node) << 
    ", "          << GetNodeTypeText(GetNodeType(Node)) <<
    std::endl;
}
template<typename T>
void PrintPreorder(const TNode<T>* Node)
{
//  0 1 2 3 4 5 6 7 8
    if(Node == NULL) return;
    std::cout << " " << Node->Value();
    PrintPreorder(Node->Left());
    PrintPreorder(Node->Right());
}
template<typename T>
void PrintInorder(const TNode<T>* Node)
{
//  2 1 3 0 6 5 7 4 8
    if(Node == NULL) return;
    PrintInorder(Node->Left());
    std::cout << " " << Node->Value();
    PrintInorder(Node->Right());
}
template<typename T>
void PrintPostorder(const TNode<T>* Node)
{
//  2 3 1 6 7 5 8 4 0
    if(Node == NULL) return;
    PrintPostorder(Node->Left());
    PrintPostorder(Node->Right());
    std::cout << Node->Value();
    if(Node->Parent()){
        std::cout << " ";
    }else{
        std::cout << std::endl;
    }
}

template<typename T, typename TIt>
void AddNode(TNode<T>* Node, TIt& PreBegin, TIt PreEnd, TIt InBegin, TIt InEnd);

template<typename T, typename TIt>
void AddLeftNode(TNode<T>* Node, TIt& PreBegin, TIt PreEnd, TIt InBegin, TIt InEnd)
{
    if(PreBegin == PreEnd) return;
    if(InBegin == InEnd) return;
    TNode<T>* New = new TNode<T>(*PreBegin);
    Node->SetLeft(New);
    AddNode(New, ++PreBegin, PreEnd, InBegin, InEnd);
}

template<typename T, typename TIt>
void AddRightNode(TNode<T>* Node, TIt& PreBegin, TIt PreEnd, TIt InBegin, TIt InEnd)
{
    if(PreBegin == PreEnd) return;
    if(InBegin == InEnd) return;
    TNode<T>* New = new TNode<T>(*PreBegin);
    Node->SetRight(New);
    AddNode(New, ++PreBegin, PreEnd, InBegin, InEnd);
}

template<typename T, typename TIt>
void AddNode(TNode<T>* Node, TIt& PreBegin, TIt PreEnd, TIt InBegin, TIt InEnd)
{
    if(PreBegin == PreEnd)  return;
    TIt It = std::find(InBegin, InEnd, Node->Value());
    assert(It != InEnd);
    AddLeftNode(Node, PreBegin, PreEnd, InBegin, It);
    AddRightNode(Node, PreBegin, PreEnd, It+1, InEnd);
}

template<typename T>
class TBinaryTree
{
    TNode<T>* FRoot;
public:
    TBinaryTree()
    {
        FRoot = NULL;
    }
    TNode<T>* Insert(const T& Value)
    {
        TNode<T>* New = new TNode<T>(Value);
        TNode<T>* Parent = NULL;
        TNode<T>* Node = FRoot;
        while(Node){
            Parent = Node;
            if(New->Value() < Node->Value()){
                Node = Node->Left();
            }else{
                Node = Node->Right();
            }
        }
        New->SetParent(Node);
        if(Parent == NULL){
            FRoot = New;
        }else if(New->Value() < Parent->Value()){
            Parent->SetLeft(New);
        }else{
            Parent->SetRight(New);
        }
        return New;
    }
    void Print()
    {
        PrintInorder(FRoot);
        std::cout << std::endl;
        PrintPreorder(FRoot);
        std::cout << std::endl;
    }
};

int main()
{
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    int n;
    std::cin >> n;
    TBinaryTree<int> Tree;
    for(std::size_t i = 0; i < n; ++i){
        std::string Command;
        std::cin >> Command;
        if(Command[0] == 'i'){
            int Value;
            std::cin >> Value;
            Tree.Insert(Value);
        }else{
            Tree.Print();
        }
    }
    return 0;
}

Measured memory_bytes: 26584