#include <iostream>
#include <iomanip>
#include <string>
#include <cstring>
#include <vector>

using namespace std;

bool trace = false;

class node
{ protected:
    string data;
    vector <node *> child;

  public:
    node(string d)
    { data = d; }

    node * add(node * p)
    { child.push_back(p);
      return this; }

    string getdata()
    { return data; }

    int getnumchildren()
    { return child.size(); }

    node * get(int i)
    { return child[i]; } };

node * mn(string s)   // mn calls constructor, but it's shorter to type
{ return new node(s); }

struct AR
{ int pos;
  string s;
  node * p;
  int depth, num, i;

  AR(int ipos, const string & is)
  { pos = ipos;
    s = is; }

  AR(int ipos, node * ip, int id = 0)
  { pos = ipos;
    p = ip;
    depth = id; }
    
  void print()
  { if (pos <= 2)
      cout << "reverse, pos = " << pos << ", s = \"" << s << "\"\n";
    else
      cout << "print, pos = " << pos << ", p = " << p << ", depth = " << depth << ", num = " << num << ", i = " << i << "\n"; } };

struct queue
{ vector <AR *> q;
  int size, num, begin, end;

  queue()
  { size = 4;
    q.resize(size);
    num = 0;
    begin = 0;
    end = 0; }

  bool empty()
  { return num == 0; }

  void grow()
  { int newsize;
    if (size == 0)
      newsize = 1;
    else
      newsize = size * 2;
    q.resize(newsize);
    if (begin >= end)
    { for (int i = size - 1; i >= begin; i -= 1)
        q[size + i] = q[i];
      begin += size; }
    size = newsize; }

  void enqueue(AR * a)
  { if (num == size)
      grow();
    q[end] = a;
    end += 1;
    if (end == size)
      end = 0;
    num += 1; }

  AR * first()
  { return q[begin]; }

  AR * dequeue()
  { AR * a = q[begin];
    begin += 1;
    if (begin == size)
      begin = 0;
    num -= 1;
    return a; }
  
  void print()
  { cout << "\n";
    int c = 0, p = begin;
    while (c < num)
    { cout << c << ": ";
      q[p]->print();
      c += 1;
      p += 1;
      if (p == size)
        p = 0; } } };

//          string reverse(const string & s)
//          { /* position 1 */
//            if (s.length() <= 1)
//              return s;
//            return reverse(s.substr(1))
//                                       /* position 2 */
//                                                       + s[0]; }
//
//          void print(node * p, int depth = 0)
//          { /* position 3 */
//            cout << setw(depth * 5) << "" << reverse(p->getdata())
//                                                                  /* position 4 */
//                                                                                  << "\n";
//            int num = p->getnumchildren();
//            int i = 0;
//            while (i < num)
//            { print(p->get(i), depth + 1);
//              /* position 5 */
//              i += 1; } }

void nonrec(node * root)
{ string result;
  queue q;
  q.enqueue(new AR(3, root));
  
  while (! q.empty())
  { if (trace)
      q.print();
    AR * a = q.first();
    switch (a->pos)
    { 
      case 1:
      { if (a->s.length() <= 1)
        { result = a->s;
          q.dequeue();
          break; }
        q.enqueue(new AR(1, a->s.substr(1)));
        a->pos = 2;
        break; }

      case 2:
      { result = result + a->s[0];
        q.dequeue();
        break; }

      case 3:
      { cout << setw(a->depth * 5) << "";
        q.enqueue(new AR(1, a->p->getdata()));
        a->pos = 4;
        break; }

      case 4:
      { cout << result << "\n";
        a->num = a->p->getnumchildren();
        a->i = 0;
        if (a->i < a->num)
        { q.enqueue(new AR(3, a->p->get(a->i), a->depth + 1));
          a->pos = 5;
          break; }
        q.dequeue();
        break; }

      case 5:
      { a->i += 1;
        if (a->i < a->num)
        { q.enqueue(new AR(3, a->p->get(a->i), a->depth + 1));
          a->pos = 5;
          break; }
        q.dequeue();
        break; } } } }

int main(int argc, char * argv[]) 
{ if (argc == 2 && strcmp(argv[1], "trace") == 0)
    trace = true;
  else if (argc != 1)
  { cerr << "usage: " << argv[0] << " [trace]\n";
    exit(1); }
  node * t = mn("ant")
                      ->add(mn("bat")
                                     ->add(mn("egg")
                                                    ->add(mn("kit"))
                                                    ->add(mn("log")))
                                     ->add(mn("fig"))
                                     ->add(mn("git")
                                                    ->add(mn("map"))
                                                    ->add(mn("nut"))
                                                    ->add(mn("old"))
                                                    ->add(mn("pig"))))
                      ->add(mn("cat")
                                     ->add(mn("hat")))
                      ->add(mn("dog")
                                     ->add(mn("ink")
                                                    ->add(mn("qat"))
                                                    ->add(mn("rat")))
                                     ->add(mn("jug")
                                                    ->add(mn("sud"))
                                                    ->add(mn("tip"))));
  nonrec(t); }