#include <stdio.h>
#include <vector>
#include <list>
#include <map>
#include <array>
#include <memory>
#include <string>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <cmath>
#include <unordered_map>
#include <stdexcept>


using std::string;
using std::vector;


//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// util
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

std::vector<std::string> split(const std::string& input, char delimiter)
{
    std::istringstream stream(input);

    std::string field;
    std::vector<std::string> result;
    while (std::getline(stream, field, delimiter)) {
        result.push_back(field);
    }
    return result;
}



//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// user func
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

void printList(const vector<int>& list) {
    // print
    for(int i = 0; i < list.size(); i++){
        printf(" %d", list[i]);
    }
    printf("\n");
}



//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// logic
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

class Node{
public:
    Node(int value)
        :value(value)
    {
    }
    int Value(){
        return this->value;
    }
    std::shared_ptr<Node> Left(){
        return this->left;
    }
    void Left(std::shared_ptr<Node> left){
        this->left = left;
    }
    std::shared_ptr<Node> Right(){
        return this->right;
    }
    void Right(std::shared_ptr<Node> right){
        this->right = right;
    }
    bool HasLeft(){
        return this->left ? true : false;
    }
    bool HasRight(){
        return this->right ? true : false;
    }

private:
    int value;
    std::shared_ptr<Node> left = nullptr ;
    std::shared_ptr<Node> right = nullptr;
};

using NodePtr = std::shared_ptr<Node>;

class BinarySearchTree{
public:
    void Insert(int value){
        if(!this->root){
            root = std::make_shared<Node>(value);
            return;
        }
        InsertProc(this->root, value);
    }
    vector<int> Preorder(){
        vector<int> result;
        this->PreorderProc(this->root, result);
        return result;
    }
    vector<int> Inorder(){
        vector<int> result;
        this->InorderProc(this->root, result);
        return result;
    }
private:
    NodePtr root = nullptr;

    void InsertProc(NodePtr node, int value){
        if(node->Value() < value){
            if(node->HasRight()){
                InsertProc(node->Right(), value);
            }else{
                node->Right(std::make_shared<Node>(value));
            }
        }else{
            if(node->HasLeft()){
                InsertProc(node->Left(), value);
            }else{
                node->Left(std::make_shared<Node>(value));
            }
        }
    }

    void PreorderProc(NodePtr current, vector<int>& list){
        list.push_back(current->Value());
        if (current->HasLeft()) PreorderProc(current->Left(), list);
        if (current->HasRight()) PreorderProc(current->Right(), list);
    }
    
    void InorderProc(NodePtr current, vector<int>& list){
        if(!current->HasLeft() && !current->HasRight()){
            list.push_back(current->Value());
            return;
        }
        if (current->HasLeft()){
            InorderProc(current->Left(), list);
        }
        list.push_back(current->Value());
        if (current->HasRight()) {
            InorderProc(current->Right(), list);
        }
    }

};

void solve() {
    // binary trees
    int n;
    scanf("%d", &n);
    BinarySearchTree tree;
    for(int i = 0; i < n; i++){
        char buffer[127];
        scanf("%s", buffer);
        string command(buffer);
        if(command == "insert"){
            int v;
            scanf(" %d", &v);
            tree.Insert(v);
        } else if(command == "print"){
            auto in = tree.Inorder();
            printList(in);
            auto pre = tree.Preorder();
            printList(pre);
        }

    }
        
}


//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// main
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
int main() {
    solve();
    return 0;
}


Measured memory_bytes: 39188