#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 stack
{ vector <AR *> s;

  bool empty()
  { return s.size() == 0; }

  void push(AR * a)
  { s.push_back(a); }

  AR * top()
  { return s.back(); }

  AR * pop()
  { AR * a = s.back();
    s.pop_back();
    return a; }
  
  void print()
  { cout << "\n";
    for (int i = 0; i < s.size(); i += 1)
    { cout << i << ": ";
      s[i]->print(); } } };

//          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;
//            /* position 5, for convenience only */
//            while (i < num)
//            { print(p->get(i), depth + 1);
//              /* position 6 */
//              i += 1; } }

void nonrec(node * root)
{ string result;
  stack stk;
  stk.push(new AR(3, root));
  
  while (! stk.empty())
  { if (trace)
      stk.print();
    AR * a = stk.top();
    switch (a->pos)
    { 
      case 1:
      { if (a->s.length() <= 1)
        { result = a->s;
          stk.pop();
          break; }
        stk.push(new AR(1, a->s.substr(1)));
        a->pos = 2;
        break; }

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

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

      case 4:
      { cout << result << "\n";
        a->num = a->p->getnumchildren();
        a->i = 0;
        a->pos = 5;
        break; }

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

      case 6:
      { a->i += 1;
        a->pos = 5;
        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); }