#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 500000

struct Node
{
  int key;
  struct Node *parent, *left, *right;
};

struct Node *root, *NIL;

void inorder(struct Node *u)
{
  if(u == NIL)return;
  inorder(u->left);
  printf(" %d",u->key);
  inorder(u->right);
}

void preorder(struct Node *u)
{
  if(u == NIL)return;
  printf(" %d",u->key);
  preorder(u->left);
  preorder(u->right);
}

void insert(int k)
{
  struct Node *y = NIL;//xの親
  struct Node *x = root;//Treeの根
  struct Node *z;

  z = (struct Node *)malloc(sizeof(struct Node));//挿入接点の設定
  z->key=k;
  z->left=NIL;
  z->right=NIL;

  while(x!=NIL)
  {
    y=x;//起点設定
    if(z->key < x->key)x = x->left;//左の子へ移動
    else x = x->right;//右の子に移動
  }
  z->parent = y;//親に接続

  if (y==NIL)//根が空の時
      root = z;

  else if(z->key < y->key)
      y->left = z; // z を y の左の子にする
  else
      y->right = z; // z を y の右の子にする
}

int main()
{
  int n,i,x;
  char str[10];

  scanf("%d",&n);

  for(i=0;i<n;i++)
  {
    scanf("%s",str);
    if(str[0]=='i')
    {
      scanf("%d",&x);
      insert(x);
    }
    else if(str[0]=='p')
    {
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }
  }
  return 0;
}

