/**
 * @copyright (c) 2020 Daisuke Hashimoto
 */

#include <cstdint>
#include <iostream>
#include <string>

constexpr int32_t kMaxNumberOfNodes = 500000;
constexpr int32_t kTop = -1;
constexpr int32_t kInvalid = -2;

enum class NodeType : int32_t { kInternal = 0, kLeaf, kRoot };

void CallBinarySearchTree(std::istream &input_stream);

enum class InstructionType : int32_t { kInsert = 0, kPrint };

InstructionType JudgeInstructionType(const std::string &str);

class Node {
 public:
  Node() noexcept;
  ~Node() noexcept;
  Node(const Node &obj) noexcept;
  Node &operator=(const Node &rhs) noexcept;
  Node(Node &&obj) noexcept;
  Node &operator=(Node &&rhs) noexcept;

  void Activate() noexcept;
  bool IsValid() const noexcept;
  void Reset() noexcept;
  void SetKey(const int32_t key);
  int32_t GetKey() const;
  void SetParent(const int32_t parent);
  int32_t GetParent() const noexcept;
  void SetChildLeft(const int32_t child_left);
  int32_t GetChildLeft() const noexcept;
  void SetChildRight(const int32_t child_right);
  int32_t GetChildRight() const noexcept;
  NodeType GetNodeType() const;
  bool DoesNotHaveAnyChildren() const noexcept;
  int32_t GetDegree() const noexcept;

  static bool IsInvalidNodeIndex(const int32_t index) noexcept;
  static bool IsValidNodeIndex(const int32_t index) noexcept;
  static bool IsInvalidParent(const int32_t parent_index) noexcept;

 private:
  bool is_valid_;
  int32_t parent_;
  int32_t child_left_;
  int32_t child_right_;
  int32_t key_;
};

class BinarySearchTree {
 public:
  BinarySearchTree() noexcept;
  ~BinarySearchTree() noexcept;

  void Insert(const int32_t key);
  void Print() const;
  void Debug() const;

 private:
  int32_t AllocateNode(const int32_t key);
  void InsertToChild(const int32_t inserted_index, const int32_t parent_index);
  void MapLeftChild(const int32_t parent_index, const int32_t left_child_index);
  void MapRightChild(const int32_t parent_index, const int32_t right_child_index);

  int32_t CalculateDepth(const int32_t index_node) const;
  int32_t CalculateHeight(const int32_t index_node) const;
  void SetTopNode(const int32_t top_node_index);
  int32_t GetSibling(const int32_t index) const;

  void WalkPreorder(const int32_t node_index) const;
  void WalkInorder(const int32_t node_index) const;

  BinarySearchTree(const BinarySearchTree &obj) = delete;
  BinarySearchTree &operator=(const BinarySearchTree &obj) = delete;
  BinarySearchTree(BinarySearchTree &&obj) = delete;
  BinarySearchTree &operator=(BinarySearchTree &&obj) = delete;

 private:
  int32_t root_;
  int32_t size_;
  Node nodes_[kMaxNumberOfNodes];
};

void CallBinarySearchTree(std::istream &input_stream) {
  input_stream.tie(0);
  std::ios::sync_with_stdio(false);
  BinarySearchTree *binary_search_tree = new BinarySearchTree();
  try {
    int32_t number_of_instructions;
    input_stream >> number_of_instructions;
    for (int32_t index_instruction = 0; index_instruction < number_of_instructions; ++index_instruction) {
      std::string instruction_str;
      input_stream >> instruction_str;
      const InstructionType instruction = JudgeInstructionType(instruction_str);
      switch (instruction) {
        case InstructionType::kInsert:
          int32_t key;
          input_stream >> key;
          binary_search_tree->Insert(key);
          break;
        case InstructionType::kPrint:
          binary_search_tree->Print();
          break;
        default:
          std::cerr << "ERROR: CallDictionary(): Invalid instruction type." << std::endl;
          break;
      }
    }
  } catch (...) {
    std::cerr << "ERROR: CallBinarySearchTree()" << std::endl;
    binary_search_tree->Debug();
    throw;
  }
  delete binary_search_tree;
}

// ****************************************************

InstructionType JudgeInstructionType(const std::string &str) {
  InstructionType instruction_type;
  if (str == "insert") {
    instruction_type = InstructionType::kInsert;
  } else if (str == "print") {
    instruction_type = InstructionType::kPrint;
  } else {
    std::cerr << "ERROR: JudgeInstructionType(): Invalid input data. " << str << std::endl;
    throw 1;
  }
  return instruction_type;
}

// ****************************************************

BinarySearchTree::BinarySearchTree() noexcept : root_(kInvalid), size_(0) {}
BinarySearchTree::~BinarySearchTree() noexcept {}

void BinarySearchTree::Insert(const int32_t key) {
  int32_t current_node_index;
  const int32_t index = AllocateNode(key);

  if (Node::IsInvalidNodeIndex(root_)) {
    SetTopNode(index);
  } else {
    InsertToChild(index, root_);
  }
}

void BinarySearchTree::InsertToChild(const int32_t inserted_index, const int32_t parent_index) {
  try {
    const Node &parent_node = nodes_[parent_index];
    const int32_t key = nodes_[inserted_index].GetKey();
    if (key < parent_node.GetKey()) {
      const int32_t next_parent = parent_node.GetChildLeft();
      if (Node::IsInvalidNodeIndex(next_parent)) {
        MapLeftChild(parent_index, inserted_index);
      } else {
        InsertToChild(inserted_index, next_parent);
      }
    } else {
      const int32_t next_parent = parent_node.GetChildRight();
      if (Node::IsInvalidNodeIndex(next_parent)) {
        MapRightChild(parent_index, inserted_index);
      } else {
        InsertToChild(inserted_index, next_parent);
      }
    }
  } catch (...) {
    std::cerr << "ERROR: InsertToChild()" << std::endl;
    throw;
  }
}

int32_t BinarySearchTree::AllocateNode(const int32_t key) {
  if (size_ >= kMaxNumberOfNodes) {
    std::cerr << "ERROR: AllocateNode(): Data size exceeded a limit = " << kMaxNumberOfNodes << std::endl;
    throw 1;
  }
  const int32_t node_index = size_;
  nodes_[node_index].Activate();
  nodes_[node_index].SetKey(key);
  size_++;
  return node_index;
}

void BinarySearchTree::MapLeftChild(const int32_t parent_index, const int32_t left_child_index) {
  if (Node::IsInvalidNodeIndex(parent_index)) {
    std::cerr << "ERROR: MapLeftChild(): Invalid arg: parent_index = " << parent_index << std::endl;
    throw 1;
  } else if (Node::IsInvalidNodeIndex(left_child_index)) {
    std::cerr << "ERROR: MapLeftChild(): Invalid arg: left_child_index = " << left_child_index << std::endl;
    throw 1;
  } else {
    try {
      nodes_[left_child_index].SetParent(parent_index);
      nodes_[parent_index].SetChildLeft(left_child_index);
    } catch (...) {
      std::cerr << "ERROR: MapLeftChild()" << std::endl;
      throw;
    }
  }
}

void BinarySearchTree::MapRightChild(const int32_t parent_index, const int32_t right_child_index) {
  if (Node::IsInvalidNodeIndex(parent_index)) {
    std::cerr << "ERROR: MapRightChild(): Invalid arg: parent_index = " << parent_index << std::endl;
    throw 1;
  } else if (Node::IsInvalidNodeIndex(right_child_index)) {
    std::cerr << "ERROR: MapRightChild(): Invalid arg: right_child_index = " << right_child_index << std::endl;
    throw 1;
  } else {
    try {
      nodes_[right_child_index].SetParent(parent_index);
      nodes_[parent_index].SetChildRight(right_child_index);
    } catch (...) {
      std::cerr << "ERROR: MapRightChild()" << std::endl;
      throw;
    }
  }
}

void BinarySearchTree::Print() const {
  try {
    WalkInorder(root_);
    std::cout << std::endl;
    WalkPreorder(root_);
    std::cout << std::endl;
  } catch (...) {
    std::cerr << "ERROR: Print()" << std::endl;
    throw;
  }
}

void BinarySearchTree::WalkPreorder(const int32_t node_index) const {
  // Preorder Tree Walk (先行順巡回)
  if (Node::IsInvalidNodeIndex(node_index)) {
    std::cerr << "ERROR: WalkPreorder(): Invalid arg node_index = " << node_index << std::endl;
    throw 1;
  }
  try {
    std::cout << " " << nodes_[node_index].GetKey();

    const int32_t left_child = nodes_[node_index].GetChildLeft();
    if (Node::IsValidNodeIndex(left_child)) {
      WalkPreorder(left_child);
    }

    const int32_t right_child = nodes_[node_index].GetChildRight();
    if (Node::IsValidNodeIndex(right_child)) {
      WalkPreorder(right_child);
    }
  } catch (...) {
    std::cerr << "ERROR: WalkPreorder()" << std::endl;
    throw 1;
  }
}

void BinarySearchTree::WalkInorder(const int32_t node_index) const {
  // Inorder Tree Walk (中間順巡回)
  if (Node::IsInvalidNodeIndex(node_index)) {
    std::cerr << "ERROR: WalkInorder(): Invalid arg node_index = " << node_index << std::endl;
    throw 1;
  }
  try {
    const int32_t left_child = nodes_[node_index].GetChildLeft();
    if (Node::IsValidNodeIndex(left_child)) {
      WalkInorder(left_child);
    }

    std::cout << " " << nodes_[node_index].GetKey();

    const int32_t right_child = nodes_[node_index].GetChildRight();
    if (Node::IsValidNodeIndex(right_child)) {
      WalkInorder(right_child);
    }
  } catch (...) {
    std::cerr << "ERROR: WalkInorder()" << std::endl;
    throw 1;
  }
}

int32_t BinarySearchTree::GetSibling(const int32_t index) const {
  int32_t sibling;
  if (Node::IsInvalidNodeIndex(index)) {
    std::cerr << "ERROR: GetSibling(): Invalid arg index = " << index << std::endl;
    throw 1;
  }
  try {
    const int32_t parent_index = nodes_[index].GetParent();
    if (parent_index == kTop) {
      sibling = -1;
    } else {
      const Node &parent = nodes_[parent_index];
      if (parent.GetChildLeft() == index) {
        sibling = parent.GetChildRight() >= 0 ? parent.GetChildRight() : -1;
      } else {
        sibling = parent.GetChildLeft() >= 0 ? parent.GetChildLeft() : -1;
      }
    }
  } catch (...) {
    std::cerr << "ERROR: GetSibling()" << std::endl;
    throw;
  }
  return sibling;
}

int32_t BinarySearchTree::CalculateDepth(const int32_t index_node) const {
  if (Node::IsInvalidNodeIndex(index_node)) {
    std::cerr << "ERROR: CalculateDepth(): Invalid arg index = " << index_node << std::endl;
    throw 1;
  }
  int32_t depth = 0;
  int32_t current_index_node = index_node;
  bool was_found = false;
  try {
    for (int32_t i = 0; i < size_; ++i) {
      const int32_t parent_node_index = nodes_[current_index_node].GetParent();
      if (parent_node_index == kTop) {
        was_found = true;
        break;
      } else {
        current_index_node = parent_node_index;
        ++depth;
      }
    }
  } catch (...) {
    std::cerr << "ERROR: CalculateDepth()" << std::endl;
    throw;
  }
  if (!was_found) {
    std::cerr << "ERROR: CalculateDepth(): root was not found. index=" << index_node << std::endl;
    throw 1;
  }
  return depth;
}

int32_t BinarySearchTree::CalculateHeight(const int32_t index_node) const {
  if (Node::IsInvalidNodeIndex(index_node)) {
    std::cerr << "ERROR: CalculateHeight(): Invalid arg index = " << index_node << std::endl;
    throw 1;
  }
  int32_t height = 0;
  try {
    const int32_t index_child_left = nodes_[index_node].GetChildLeft();
    int32_t height_from_left = 0;
    if (Node::IsValidNodeIndex(index_child_left)) {
      height_from_left = 1 + CalculateHeight(index_child_left);
    }

    const int32_t index_child_right = nodes_[index_node].GetChildRight();
    int32_t height_from_right = 0;
    if (Node::IsValidNodeIndex(index_child_right)) {
      height_from_right = 1 + CalculateHeight(index_child_right);
    }
    height = height_from_left > height_from_right ? height_from_left : height_from_right;
  } catch (...) {
    std::cerr << "ERROR: CalculateHeight()" << std::endl;
    throw;
  }
  return height;
}

void BinarySearchTree::SetTopNode(const int32_t top_node_index) {
  try {
    nodes_[top_node_index].SetParent(kTop);
    root_ = top_node_index;
  } catch (...) {
    std::cerr << "ERROR: SetTopNode()" << std::endl;
    throw;
  }
}

void BinarySearchTree::Debug() const {
  const char node_type_str[][20] = {"internal node", "leaf", "root"};
  try {
    std::cerr << "Number of nodes = " << size_ << std::endl;
    std::cerr << "Root = " << root_ << std::endl;
    for (int32_t current_node_index = 0; current_node_index < size_; ++current_node_index) {
      const Node &cnode = nodes_[current_node_index];
      std::cerr << "node " << current_node_index << ": ";
      std::cerr << "key = " << nodes_[current_node_index].GetKey() << ", ";
      std::cerr << "parent = " << cnode.GetParent() << ", ";
      std::cerr << "sibling = " << GetSibling(current_node_index) << ", ";
      std::cerr << "degree = " << cnode.GetDegree() << ", ";
      std::cerr << "depth = " << CalculateDepth(current_node_index) << ", ";
      std::cerr << "height = " << CalculateHeight(current_node_index) << ", ";
      std::cerr << node_type_str[static_cast<int32_t>(cnode.GetNodeType())] << std::endl;
    }
  } catch (...) {
    std::cerr << "ERROR: Debug()" << std::endl;
    throw;
  }
}

// ****************************************************
Node::Node() noexcept : is_valid_(false), parent_(kInvalid), child_left_(kInvalid), child_right_(kInvalid), key_(0) {}

Node::~Node() noexcept {}

Node::Node(const Node &obj) noexcept
    : is_valid_(obj.is_valid_),
      parent_(obj.parent_),
      child_left_(obj.child_left_),
      child_right_(obj.child_right_),
      key_(obj.key_) {}

Node &Node::operator=(const Node &rhs) noexcept {
  if (this != &rhs) {
    this->is_valid_ = rhs.is_valid_;
    this->parent_ = rhs.parent_;
    this->child_left_ = rhs.child_left_;
    this->child_right_ = rhs.child_right_;
    this->key_ = rhs.key_;
  }
  return *this;
}

Node::Node(Node &&obj) noexcept
    : is_valid_(obj.is_valid_),
      parent_(obj.parent_),
      child_left_(obj.child_left_),
      child_right_(obj.child_right_),
      key_(obj.key_) {
  obj.Reset();
}

Node &Node::operator=(Node &&rhs) noexcept {
  if (this != &rhs) {
    this->is_valid_ = rhs.is_valid_;
    this->parent_ = rhs.parent_;
    this->child_left_ = rhs.child_left_;
    this->child_right_ = rhs.child_right_;
    this->key_ = rhs.key_;
    rhs.Reset();  // 無効化
  }
  return *this;
}

void Node::Reset() noexcept {
  this->is_valid_ = false;
  this->parent_ = kInvalid;
  this->child_left_ = kInvalid;
  this->child_right_ = kInvalid;
  this->key_ = 0;
}

void Node::Activate() noexcept {
  is_valid_ = true;
}

bool Node::IsValid() const noexcept {
  return is_valid_;
}

void Node::SetKey(const int32_t key) {
  if (!IsValid()) {
    std::cerr << "ERROR: SetKey(): Not valid node." << std::endl;
    throw 1;
  }
  key_ = key;
}

int32_t Node::GetKey() const {
  if (!IsValid()) {
    std::cerr << "ERROR: GetKey(): Not valid node." << std::endl;
    throw 1;
  }
  return key_;
}

void Node::SetParent(const int32_t parent) {
  try {
    if (IsInvalidParent(parent)) {
      std::cerr << "ERROR: SetParent(): Invalid arg: parent = " << parent << std::endl;
      throw 1;
    }
    parent_ = parent;
  } catch (...) {
    std::cerr << "ERROR: SetParent()" << std::endl;
    throw;
  }
}

int32_t Node::GetParent() const noexcept {
  return parent_;
}

bool Node::IsInvalidParent(const int32_t parent_index) noexcept {
  return ((parent_index != kTop) && IsInvalidNodeIndex(parent_index));
}

void Node::SetChildLeft(const int32_t child_left) {
  if (IsInvalidNodeIndex(child_left)) {
    std::cerr << "ERROR: SetChildLeft(): Invalid arg: child_left = " << child_left << std::endl;
    throw 1;
  } else if (IsValidNodeIndex(child_left_)) {
    std::cerr << "ERROR: SetChildLeft(): child_left_ is already configured." << std::endl;
    throw 1;
  } else {
    child_left_ = child_left;
  }
}

int32_t Node::GetChildLeft() const noexcept {
  return child_left_;
}

void Node::SetChildRight(const int32_t child_right) {
  if (IsInvalidNodeIndex(child_right)) {
    std::cerr << "ERROR: SetChildRight(): Invalid arg: child_right = " << child_right << std::endl;
    throw 1;
  } else if (IsValidNodeIndex(child_right_)) {
    std::cerr << "ERROR: SetChildRight(): child_right_ is already configured." << std::endl;
    throw 1;
  } else {
    child_right_ = child_right;
  }
}

int32_t Node::GetChildRight() const noexcept {
  return child_right_;
}

int32_t Node::GetDegree() const noexcept {
  int32_t degree = 0;
  degree += IsValidNodeIndex(GetChildLeft()) ? 1 : 0;
  degree += IsValidNodeIndex(GetChildRight()) ? 1 : 0;
  return degree;
}

bool Node::DoesNotHaveAnyChildren() const noexcept {
  const bool does_not_have_left_child = IsInvalidNodeIndex(GetChildLeft());
  const bool does_not_have_right_child = IsInvalidNodeIndex(GetChildRight());
  return (does_not_have_left_child && does_not_have_right_child);
}

NodeType Node::GetNodeType() const {
  if (!IsValid()) {
    std::cerr << "ERROR: GetNodeType(): Not valid node." << std::endl;
    throw 1;
  }
  NodeType node_type;
  if (parent_ == kTop) {
    node_type = NodeType::kRoot;
  } else if (parent_ == kInvalid) {
    std::cerr << "ERROR: GetNodeType(): Invalid parent." << std::endl;
    throw 1;
  } else if (DoesNotHaveAnyChildren()) {
    node_type = NodeType::kLeaf;
  } else {
    node_type = NodeType::kInternal;
  }
  return node_type;
}

bool Node::IsInvalidNodeIndex(const int32_t index) noexcept {
  return ((index < 0) || (index >= kMaxNumberOfNodes));
}

bool Node::IsValidNodeIndex(const int32_t index) noexcept {
  return !IsInvalidNodeIndex(index);
}

int main(int argc, char *argv[]) {
  try {
    CallBinarySearchTree(std::cin);
  } catch (...) {
    std::cerr << "ERROR: main()" << std::endl;
  }
  return 0;
}



Measured memory_bytes: 12508