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

struct node {
  int key;
  struct node *parent;
  struct node *left;
  struct node *right;
};

struct node *tree = NULL;

void insert(struct node **root, struct node *node)
{
  struct node *parent = NULL;
  struct node *current = *root;

  while (current != NULL) {
    parent = current;
    if (node->key < current->key) {
      current = current->left;
    } else {
      current = current->right;
    }
  }

  node->parent = parent;

  if (parent == NULL) {
    *root = node;
  } else if (node->key < parent->key) {
    parent->left = node;
  } else {
    parent->right = node;
  }
}
void preorder_traverse(struct node* node)
{
  if (node != NULL) {
    printf("%d ", node->key);
    preorder_traverse(node->left);
    preorder_traverse(node->right);
  }
}

void inorder_traverse(struct node *node)
{
  if (node != NULL) {
    inorder_traverse(node->left);
    printf("%d ", node->key);
    inorder_traverse(node->right);
  }
}

int main (int argc, char** argv)
{
  int i, num;
  char str[32] = {0};
  fgets(str, 32, stdin);
  num = atoi(str);
  for (i = 0; i < num; i++) {
    fgets(str, 32, stdin);
    strtok(str, "\r\n");
    if (strstr(str, "insert")) {
      struct node *node = (struct node *)malloc(sizeof(struct node));
      node->key = atoi(&str[7]);
      node->left = NULL;
      node->right = NULL;
      insert(&tree, node);
    } else if (strstr(str, "print")) {
      inorder_traverse(tree);
      printf("\n");
      preorder_traverse(tree);
      printf("\n");
    }
  }
  return 0;
}