import std.algorithm, std.conv, std.range, std.stdio, std.string;

void main()
{
  auto n = readln.chomp.to!size_t;
  Node node;

  foreach (_; n.iota) {
    auto rd = readln.chomp.splitter(' '), cmd = rd.front;
    switch (cmd) {
    case "insert":
      rd.popFront;
      node.insert(rd.front.to!int);
      break;
    case "print":
      node.inorderWalk;
      writeln;
      node.preorderWalk;
      writeln;
      break;
    default:
      assert(0);
    }
  }
}

void writeArray(T)(T[] ai)
{
  foreach (a; ai) write(" ", a);
  writeln;
}

void insert(ref Node node, int val)
{
  Node par, cur = node;
  while (cur !is null) {
    par = cur;
    if (val < cur.key) cur = cur.l;
    else cur = cur.r;
  }

  Node chi = new Node(val);
  if (par is null)
    node = chi;
  else if (val < par.key)
    par.l = chi;
  else
    par.r = chi;
}

void inorderWalk(Node node)
{
  if (node.l !is null) inorderWalk(node.l);
  write(" ", node.key);
  if (node.r !is null) inorderWalk(node.r);
}

void preorderWalk(Node node)
{
  write(" ", node.key);
  if (node.l !is null) preorderWalk(node.l);
  if (node.r !is null) preorderWalk(node.r);
}

class Node
{
  int key;
  Node l, r;

  this(int key)
  {
    this.key = key;
  }
}