#include <iostream>
#include <memory>
#include <string>

namespace BinarySearchTree{
using namespace std;
constexpr int nullNum = -1;

class Node{
public:
    Node( int k, shared_ptr<Node> p, shared_ptr<Node> l, shared_ptr<Node> r ) : 
    key( k ), parent( p ), left( l ), right( r ) {}

    Node( int k ) : 
    key( k ), parent( nullptr ), left( nullptr ), right( nullptr ) {}

    Node() : 
    key( nullNum ), parent( nullptr ), left( nullptr ), right( nullptr ) {}

    //----Getter----
    int Key(){
        return key;
    }

    shared_ptr<Node> Left(){
        return left;
    }

    shared_ptr<Node> Right(){
        return right;
    }

    //----Setter----
    void SetParent( shared_ptr<Node> p ){
        parent = p;
    }

    void SetLeft( shared_ptr<Node> l ){
        left = l;
    }

    void SetRight( shared_ptr<Node> r ){
        right = r;
    }

private:
    int key;
    shared_ptr<Node> parent;
    shared_ptr<Node> left;
    shared_ptr<Node> right;
};

// shared_ptr<Node> SearchByKey( shared_ptr<Node> x, int key ){
//     if( !x || key == x->Key() ){
//         return x;
//     }
//     if( key < x->Key() ){
//         return SearchByKey( x->Left(), key );
//     }else{
//         return SearchByKey( x->Right(), key );
//     }
// }

void Insert( shared_ptr<Node>& root, shared_ptr<Node>& z ){
    if( root->Key() == nullNum ){
        //std::cout << "root == nullptr : ";
        root.reset();
        root = std::move( z );
        //std::cout << root->Key() << "\n";
    }else{
        //std::cout << "root != nullptr\n";
        shared_ptr<Node> y = nullptr;
        shared_ptr<Node> x = root;
        while( x ){
            y = x;
            if( z->Key() < x->Key() ){
                x = x->Left();
            }else{
                x = x->Right();
            }
        }

        z->SetParent( y );

        if( z->Key() < y->Key() ){
            y->SetLeft( z );
        }else{
            y->SetRight( z );
        }
    }
}

void InorderTreeWalk( shared_ptr<Node> root ){
    if( root ){//怪しい
        InorderTreeWalk( root->Left() );
        std::cout << " " << root->Key();
        InorderTreeWalk( root->Right() );
    }
}

void PreorderTreeWalk( shared_ptr<Node> root ){
    if( root ){
        std::cout << " " << root->Key();
        PreorderTreeWalk( root->Left() );
        PreorderTreeWalk( root->Right() );
    }
}

}

int main(){
    std::cin.tie( 0 );

    int n;
    std::string command;
    std::getline( std::cin, command );
    n = std::stoi( command );

    int key;
    std::shared_ptr<BinarySearchTree::Node> tree = std::make_shared<BinarySearchTree::Node>();

    for( int i = 0; i < n; ++i ){
        std::getline( std::cin, command );
        if( command[0] == 'p' ){
            BinarySearchTree::InorderTreeWalk( tree );
            std::cout << "\n";
            BinarySearchTree::PreorderTreeWalk( tree );
            std::cout << std::endl;
        }else{
            key = std::stoi( &command[7] );
            std::shared_ptr<BinarySearchTree::Node> node = std::make_shared<BinarySearchTree::Node>( key );
            //std::cout << node->Key() << " ";
            BinarySearchTree::Insert( tree, node );
            //std::cout << tree->Key() << "\n";
            //Insertがうまくいかない
        }
    }
}


Measured memory_bytes: 42164