#include <cstdio>

struct node {
  int key;
  node *left, *right;
  node(int key) : key(key), left(nullptr), right(nullptr) {}
  ~node() {
    delete left;
    delete right;
  }
};

enum order {
  pre,
  in
};

void rec(node *t, order o) {
  if (!t)
    return;
  if (o == pre)
    printf(" %d", t->key);
  rec(t->left, o);
  if (o == in)
    printf(" %d", t->key);
  rec(t->right, o);
}

int main() {
  node *T(nullptr);
  size_t m;
  scanf("%zu\n", &m);
  for (size_t i = 0; i < m; i++) {
    char s[8];
    scanf("%s", s);
    if (s[0] == 'i') {
      int k;
      scanf("%d", &k);
      node *x = T, *y = nullptr, *z = new node(k);
      while (x) {
        y = x;
        x = z->key < y->key ? y->left : y->right;
      }
      (y ? z->key < y->key ? y->left : y->right : T) = z;
    } else {
      rec(T, in);
      puts("");
      rec(T, pre);
      puts("");
    }
  }
  delete T;
  return 0;
}