#include <iostream>
#include <string>
#include <cstdlib>

using namespace std;

class tree
{ protected:

  struct node
  {
    string data;
    node * left, * right;


    node(string x)
    { data = x; left = NULL; right = NULL; }


    void printall()
    { if (this == NULL)
        return;
      left->printall();
      cout << data << " ";
      right->printall(); }


    int printatdepth(int depth, int wanteddepth)
    { if (this == NULL)
        return 0;

      int count = left->printatdepth(depth + 1, wanteddepth);

      if (depth == wanteddepth)
      { cout << depth << ": " << data << "\n";
        count += 1; }

      count += right->printatdepth(depth + 1, wanteddepth);
      return count; }


    void printvisible()
    { if (this == NULL)
      { cout << "@";
        return; }
      cout << "[";
      left->printvisible();
      cout << " " << data << " ";
      right->printvisible();
      cout << "]"; }


    node * insert(string x)
    { if (this == NULL)
        return new node(x);
      else if (x == data)
      { }
      else if (x < data)
        left = left->insert(x);
      else
        right = right->insert(x);
      return this; }


    node * tracedinsert(string x)
    { if (this == NULL)
      { cout << "reached null, ending\n";
        return new node(x); }

      else if (x == data)
        cout << "repeat value, ignoring\n";

      else if (x < data)
      { cout << "looking at " << data << ", going left\n";
        left = left->tracedinsert(x); }

      else
      { cout << "looking at " << data << ", going right\n";
        right = right->tracedinsert(x); }

      cout << "end of insertion into " << data << "\n";
      return this; }


    void loopinsert(string x)  // does not need to worry about NULL parameter
    { node * curr = this;
      while (true)
      { if (x == curr->data)
          return;

        else if (x < curr->data)
        { if (curr->left == NULL)
          { curr->left = new node(x);
            return; }
          else
            curr = curr->left;  }

        else
        { if (curr->right == NULL)
          { curr->right = new node(x);
            return; }
          else
            curr = curr->right; } } } };       // end of struct node definition


            // we are still in the class tree definition now.
  public:
    node * root;


    tree()
    { root = NULL; }


    void insert(string x)
    { root = root->insert(x); }


    void tracedinsert(string x)
    { root = root->tracedinsert(x); }


    void loopinsert(string x)
    { if (root == NULL)
        root = new node(x);
      else
        root->loopinsert(x); }


    void print()
    { root->printall(); }


    void printvisible()
    { root->printvisible(); }


    void printatdepth(int d)
    { root->printatdepth(1, d); }


    void breadthfirstprint()
    { for (int wanted = 1; true; wanted += 1)
      { int printed = root->printatdepth(1, wanted);
        if (printed == 0)
          break; } }
};


int main()
{ srandomdev();
  tree T;
  for (int i = 0; i < 13; i += 1)
  { string s;
    cin >> s;
    T.insert(s); }

  cout << "normal print\n";
  T.print();
  cout << "\n\nprintvisible()\n";
  T.printvisible();
  cout << "\n\nbreadthfirstprint\n";
  T.breadthfirstprint();
  cout << "\n"; }


/*
$ cat inp
b a d c f e h g j i bat cat ghost

$ a.out < inp
normal print
a b bat c cat d e f g ghost h i j 

printvisible()
[[@ a @] b [[[@ bat @] c [@ cat @]] d [[@ e @] f [[@ g [@ ghost @]] h [[@ i @] j @]]]]]

breadthfirstprint
1: b
2: a
2: d
3: c
3: f
4: bat
4: cat
4: e
4: h
5: g
5: j
6: ghost
6: i

$
*/