#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

struct node {
  struct node *right;
  struct node *left;
  int val;
};

typedef struct node Node;

Node *root;
Node *leftMost;
int min = INT_MAX;

void insert(Node *cur, int curVal) {
  if (cur->val == -1) {
    cur->val = curVal;
    if (curVal < min) {
      min = curVal;
      leftMost = cur;
    }
  }
  else if (curVal < cur->val) {
    if(cur->left == NULL) {
      Node *new = malloc(sizeof(Node));
      new->val = -1;
      new->left = NULL;
      new->right = NULL;
      //      printf("allocated a node\n");
      cur->left = new;
    }
    insert(cur->left, curVal);
  } else {
    if(cur->right == NULL) {
      Node *new = malloc(sizeof(Node));
      new->val = -1;
      new->left = NULL;
      new->right = NULL;
      //printf("allocated a node\n");
      cur->right = new;
    }
    insert(cur->right, curVal);
  }
    insert(cur->right, curVal);
  }
}

void inorder(Node *cur){
  if (cur == NULL)
    return;

  inorder(cur->left);
  if (cur == leftMost)
    printf("%d", cur->val);
  else
    printf(" %d", cur->val);
  inorder(cur->right);
}

void preorder(Node *cur){
  if (cur == NULL)
    return;

  if (cur == root)
    printf("%d", cur->val);
  else
    printf(" %d", cur->val);
  preorder(cur->left);
  preorder(cur->right);
}

int main() {
  int commands, i, num;
  char com[20];

  root = malloc(sizeof(Node));
  root->val = -1;
  root->left = NULL;
  root->right = NULL;

  scanf("%d", &commands);

  for (i = 0; i < commands; i++) {
    scanf("%s", &com);
    if (!strcmp(com, "insert")) {
      scanf("%d", &num);
      insert(root, num);
      //printf("inserted!\n");
    } else if (!strcmp(com, "print")) {
      //printf("inserted!\n");
    } else if (!strcmp(com, "print")) {
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }
  }
}

