#include <bits/stdc++.h>
using namespace std;

class node;
node *root, *NIL;

class node{
public:
  node *p = NIL, *l = NIL, *r = NIL;
  int key = 0;

  node(int x) : key(x){}
};


void insert(int key){
  node *x = root, *y = NIL;
  while(x != NIL){
      y = x;
      if(key >= x->key) x = x->r;
      else x = x->l;
  }

  if(y == NIL) root = new node(key);
  else if(key >= y->key) y->r = new node(key);
  else y->l = new node(key);
}

void preorder(node* n){
  if(n == NIL) return;
  cout << " " << n->key;
  preorder(n->l);
  preorder(n->r);
}

void inorder(node* n){
  if(n == NIL) return;
  inorder(n->l);
  cout << " " << n->key;
  inorder(n->r);
}

void print(){
  inorder(root);
  cout << endl;
  preorder(root);
  cout << endl;
}

int main(){
  root = NIL;

  int n; cin >> n;
  while(n--){
    string s; cin >> s;

    if(s == "insert"){
      int x; cin >> x;
      insert(x);
    }else{
      print();
    }
  }
}

