#include <iostream>
#include <vector>
#include <stdexcept>
#include <utility>
 
class EndOfTheWorldAsWeKnowIt { };
 
class Disk
{
  unsigned diameter;
  void brahma_check() const
  {
    if (diameter == 0)
      throw std::logic_error("Brahma ist zornig! "
                             "Du hast die heiligen Regeln verletzt, "
                             "als du eine nicht existierende Scheibe nahmst."
                             );
  }
public:
  Disk(unsigned diameter = 0) : diameter(diameter) { }
  Disk(Disk &&other): diameter(other.diameter) 
  {
    other.brahma_check(); 
    other.diameter = 0;
  }
  Disk(const Disk&) = delete;
  void operator=(const Disk&) = delete;
  unsigned get_diameter() const { brahma_check(); return diameter; }
 
  friend std::ostream& operator<<(std::ostream &out, Disk const& disk)
  {
    return out << "|\t" << disk.diameter << "\t|";
  }
};
 
class Tower
{
  std::vector<Disk> disks;
public:
  void add_disk(Disk &&disk) 
  { 
    if (!disks.empty() && disks.back().get_diameter() < disk.get_diameter() )
      throw std::logic_error("Brahma ist zornig! "
                             "Du hast die heiligen Regeln verletzt, "
                             "als du eine große Scheibe auf eine kleine legtest."
                             );
 
 
    disks.push_back(std::move(disk)); 
  }
  Disk remove_top() 
  {
    if (disks.empty()) 
      throw std::logic_error("Brahma ist zornig! "
                             "Du hast die heiligen Regeln verletzt, "
                             "als du eine Scheibe von einem leeren Turm nahmst."
                             );
 
    Disk disk = std::move(disks.back());
    disks.pop_back();
    return std::move(disk);
  }
  bool empty() const { return disks.empty(); }
  Tower() = default;
  Tower(const Tower&) = delete;
  void operator=(const Tower&) = delete;
 
  friend std::ostream& operator<<(std::ostream &out, Tower const& tower)
  {
    for(auto const& disk: tower.disks)
      out << disk;
    return out;
  }
};
 
template <unsigned num_disks> class Temple
{
  Tower towers[3];
public:
  Temple()
  {
    for(unsigned i = num_disks; i != 0; --i)
      towers[0].add_disk(Disk(i));
  }
  void move(unsigned from, unsigned to)
  {
    towers[to].add_disk(towers[from].remove_top());
  }
  void show_to_brahma() const
  {
    if (towers[0].empty() && (towers[1].empty() || towers[2].empty()))
      throw EndOfTheWorldAsWeKnowIt();
    else
      throw std::logic_error("Brahma ist zornig! "
                             "Du hast die heiligen Regeln verletzt, "
                             "als du ihm eine unvollstandige Lösung zeigtest."
                             );
  }
 
  friend std::ostream& operator<<(std::ostream &out, Temple<num_disks> const& temple)
  {
    return out << "----------------------------------------------------------\n"
               << temple.towers[0] << '\n' 
               << temple.towers[1] << '\n'
               << temple.towers[2] << '\n'
               << "----------------------------------------------------------\n";
  }
};
 
class Monk
{
  unsigned rank;
  static unsigned other_tower(unsigned t1, unsigned t2)
  {
    if (t1 == 0 && t2 == 1) return 2;
    if (t1 == 1 && t2 == 0) return 2;
    if (t1 == 2 && t2 == 1) return 0;
    if (t1 == 1 && t2 == 2) return 0;
    if (t1 == 2 && t2 == 0) return 1;
    if (t1 == 0 && t2 == 2) return 1;
    throw std::logic_error("Brahma ist zornig! "
                           "Du hast die heiligen Regeln verletzt, "
                           "als du totalen Unsinn programmiert hast."
                           );
  }
public:
  Monk(unsigned rank): rank(rank) { }
  template <typename Temple> void solve_puzzle(Temple &temple, unsigned from, unsigned to)
  {
    if (rank > 1)
      {
        // Ask subordinate to move all the top disks:
        Monk minor_monk(rank - 1);
        unsigned other = other_tower(from, to);
        minor_monk.solve_puzzle(temple, from, other);
        // Move the last piece
        temple.move(from, to);
        // Proudly draw the result:
        std::cout << temple;
        // Ask subordinate to move all the rest:
        minor_monk.solve_puzzle(temple, other, to);        
      }
    else
      {
        // This task is simple, even for the lowliest monk:
        temple.move(from, to);
        // Proudly draw the result:
        std::cout << temple;
      }
  }
};
 
int main()
{
  const unsigned num_disks = 5;
  Temple<num_disks> temple;
  try
    {
      std::cout << temple;
      Monk abbot(num_disks);
      abbot.solve_puzzle(temple, 0, 1);
      temple.show_to_brahma();
    }
  catch (EndOfTheWorldAsWeKnowIt)
    {
      std::cout << "Brahma ist zufrieden. Das Universum hat seinen Zweck "
        "erfüllt und kann nun neu erschaffen werden. Einen schönen Tag noch!\n";
    }
}
 

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8c3RkZXhjZXB0PgojaW5jbHVkZSA8dXRpbGl0eT4KCmNsYXNzIEVuZE9mVGhlV29ybGRBc1dlS25vd0l0IHsgfTsKCmNsYXNzIERpc2sKewogIHVuc2lnbmVkIGRpYW1ldGVyOwogIHZvaWQgYnJhaG1hX2NoZWNrKCkgY29uc3QKICB7CiAgICBpZiAoZGlhbWV0ZXIgPT0gMCkKICAgICAgdGhyb3cgc3RkOjpsb2dpY19lcnJvcigiQnJhaG1hIGlzdCB6b3JuaWchICIKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAiRHUgaGFzdCBkaWUgaGVpbGlnZW4gUmVnZWxuIHZlcmxldHp0LCAiCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgImFscyBkdSBlaW5lIG5pY2h0IGV4aXN0aWVyZW5kZSBTY2hlaWJlIG5haG1zdC4iCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgKTsKICB9CnB1YmxpYzoKICBEaXNrKHVuc2lnbmVkIGRpYW1ldGVyID0gMCkgOiBkaWFtZXRlcihkaWFtZXRlcikgeyB9CiAgRGlzayhEaXNrICYmb3RoZXIpOiBkaWFtZXRlcihvdGhlci5kaWFtZXRlcikgCiAgewogICAgb3RoZXIuYnJhaG1hX2NoZWNrKCk7IAogICAgb3RoZXIuZGlhbWV0ZXIgPSAwOwogIH0KICBEaXNrKGNvbnN0IERpc2smKSA9IGRlbGV0ZTsKICB2b2lkIG9wZXJhdG9yPShjb25zdCBEaXNrJikgPSBkZWxldGU7CiAgdW5zaWduZWQgZ2V0X2RpYW1ldGVyKCkgY29uc3QgeyBicmFobWFfY2hlY2soKTsgcmV0dXJuIGRpYW1ldGVyOyB9CgogIGZyaWVuZCBzdGQ6Om9zdHJlYW0mIG9wZXJhdG9yPDwoc3RkOjpvc3RyZWFtICZvdXQsIERpc2sgY29uc3QmIGRpc2spCiAgewogICAgcmV0dXJuIG91dCA8PCAifFx0IiA8PCBkaXNrLmRpYW1ldGVyIDw8ICJcdHwiOwogIH0KfTsKCmNsYXNzIFRvd2VyCnsKICBzdGQ6OnZlY3RvcjxEaXNrPiBkaXNrczsKcHVibGljOgogIHZvaWQgYWRkX2Rpc2soRGlzayAmJmRpc2spIAogIHsgCiAgICBpZiAoIWRpc2tzLmVtcHR5KCkgJiYgZGlza3MuYmFjaygpLmdldF9kaWFtZXRlcigpIDwgZGlzay5nZXRfZGlhbWV0ZXIoKSApCiAgICAgIHRocm93IHN0ZDo6bG9naWNfZXJyb3IoIkJyYWhtYSBpc3Qgem9ybmlnISAiCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIkR1IGhhc3QgZGllIGhlaWxpZ2VuIFJlZ2VsbiB2ZXJsZXR6dCwgIgogICAgICAgICAgICAgICAgICAgICAgICAgICAgICJhbHMgZHUgZWluZSBncm/Dn2UgU2NoZWliZSBhdWYgZWluZSBrbGVpbmUgbGVndGVzdC4iCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgKTsKCgogICAgZGlza3MucHVzaF9iYWNrKHN0ZDo6bW92ZShkaXNrKSk7IAogIH0KICBEaXNrIHJlbW92ZV90b3AoKSAKICB7CiAgICBpZiAoZGlza3MuZW1wdHkoKSkgCiAgICAgIHRocm93IHN0ZDo6bG9naWNfZXJyb3IoIkJyYWhtYSBpc3Qgem9ybmlnISAiCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIkR1IGhhc3QgZGllIGhlaWxpZ2VuIFJlZ2VsbiB2ZXJsZXR6dCwgIgogICAgICAgICAgICAgICAgICAgICAgICAgICAgICJhbHMgZHUgZWluZSBTY2hlaWJlIHZvbiBlaW5lbSBsZWVyZW4gVHVybSBuYWhtc3QuIgogICAgICAgICAgICAgICAgICAgICAgICAgICAgICk7CgogICAgRGlzayBkaXNrID0gc3RkOjptb3ZlKGRpc2tzLmJhY2soKSk7CiAgICBkaXNrcy5wb3BfYmFjaygpOwogICAgcmV0dXJuIHN0ZDo6bW92ZShkaXNrKTsKICB9CiAgYm9vbCBlbXB0eSgpIGNvbnN0IHsgcmV0dXJuIGRpc2tzLmVtcHR5KCk7IH0KICBUb3dlcigpID0gZGVmYXVsdDsKICBUb3dlcihjb25zdCBUb3dlciYpID0gZGVsZXRlOwogIHZvaWQgb3BlcmF0b3I9KGNvbnN0IFRvd2VyJikgPSBkZWxldGU7CgogIGZyaWVuZCBzdGQ6Om9zdHJlYW0mIG9wZXJhdG9yPDwoc3RkOjpvc3RyZWFtICZvdXQsIFRvd2VyIGNvbnN0JiB0b3dlcikKICB7CiAgICBmb3IoYXV0byBjb25zdCYgZGlzazogdG93ZXIuZGlza3MpCiAgICAgIG91dCA8PCBkaXNrOwogICAgcmV0dXJuIG91dDsKICB9Cn07Cgp0ZW1wbGF0ZSA8dW5zaWduZWQgbnVtX2Rpc2tzPiBjbGFzcyBUZW1wbGUKewogIFRvd2VyIHRvd2Vyc1szXTsKcHVibGljOgogIFRlbXBsZSgpCiAgewogICAgZm9yKHVuc2lnbmVkIGkgPSBudW1fZGlza3M7IGkgIT0gMDsgLS1pKQogICAgICB0b3dlcnNbMF0uYWRkX2Rpc2soRGlzayhpKSk7CiAgfQogIHZvaWQgbW92ZSh1bnNpZ25lZCBmcm9tLCB1bnNpZ25lZCB0bykKICB7CiAgICB0b3dlcnNbdG9dLmFkZF9kaXNrKHRvd2Vyc1tmcm9tXS5yZW1vdmVfdG9wKCkpOwogIH0KICB2b2lkIHNob3dfdG9fYnJhaG1hKCkgY29uc3QKICB7CiAgICBpZiAodG93ZXJzWzBdLmVtcHR5KCkgJiYgKHRvd2Vyc1sxXS5lbXB0eSgpIHx8IHRvd2Vyc1syXS5lbXB0eSgpKSkKICAgICAgdGhyb3cgRW5kT2ZUaGVXb3JsZEFzV2VLbm93SXQoKTsKICAgIGVsc2UKICAgICAgdGhyb3cgc3RkOjpsb2dpY19lcnJvcigiQnJhaG1hIGlzdCB6b3JuaWchICIKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAiRHUgaGFzdCBkaWUgaGVpbGlnZW4gUmVnZWxuIHZlcmxldHp0LCAiCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgImFscyBkdSBpaG0gZWluZSB1bnZvbGxzdGFuZGlnZSBMw7ZzdW5nIHplaWd0ZXN0LiIKICAgICAgICAgICAgICAgICAgICAgICAgICAgICApOwogIH0KCiAgZnJpZW5kIHN0ZDo6b3N0cmVhbSYgb3BlcmF0b3I8PChzdGQ6Om9zdHJlYW0gJm91dCwgVGVtcGxlPG51bV9kaXNrcz4gY29uc3QmIHRlbXBsZSkKICB7CiAgICByZXR1cm4gb3V0IDw8ICItLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tXG4iCiAgICAgICAgICAgICAgIDw8IHRlbXBsZS50b3dlcnNbMF0gPDwgJ1xuJyAKICAgICAgICAgICAgICAgPDwgdGVtcGxlLnRvd2Vyc1sxXSA8PCAnXG4nCiAgICAgICAgICAgICAgIDw8IHRlbXBsZS50b3dlcnNbMl0gPDwgJ1xuJwogICAgICAgICAgICAgICA8PCAiLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLVxuIjsKICB9Cn07CgpjbGFzcyBNb25rCnsKICB1bnNpZ25lZCByYW5rOwogIHN0YXRpYyB1bnNpZ25lZCBvdGhlcl90b3dlcih1bnNpZ25lZCB0MSwgdW5zaWduZWQgdDIpCiAgewogICAgaWYgKHQxID09IDAgJiYgdDIgPT0gMSkgcmV0dXJuIDI7CiAgICBpZiAodDEgPT0gMSAmJiB0MiA9PSAwKSByZXR1cm4gMjsKICAgIGlmICh0MSA9PSAyICYmIHQyID09IDEpIHJldHVybiAwOwogICAgaWYgKHQxID09IDEgJiYgdDIgPT0gMikgcmV0dXJuIDA7CiAgICBpZiAodDEgPT0gMiAmJiB0MiA9PSAwKSByZXR1cm4gMTsKICAgIGlmICh0MSA9PSAwICYmIHQyID09IDIpIHJldHVybiAxOwogICAgdGhyb3cgc3RkOjpsb2dpY19lcnJvcigiQnJhaG1hIGlzdCB6b3JuaWchICIKICAgICAgICAgICAgICAgICAgICAgICAgICAgIkR1IGhhc3QgZGllIGhlaWxpZ2VuIFJlZ2VsbiB2ZXJsZXR6dCwgIgogICAgICAgICAgICAgICAgICAgICAgICAgICAiYWxzIGR1IHRvdGFsZW4gVW5zaW5uIHByb2dyYW1taWVydCBoYXN0LiIKICAgICAgICAgICAgICAgICAgICAgICAgICAgKTsKICB9CnB1YmxpYzoKICBNb25rKHVuc2lnbmVkIHJhbmspOiByYW5rKHJhbmspIHsgfQogIHRlbXBsYXRlIDx0eXBlbmFtZSBUZW1wbGU+IHZvaWQgc29sdmVfcHV6emxlKFRlbXBsZSAmdGVtcGxlLCB1bnNpZ25lZCBmcm9tLCB1bnNpZ25lZCB0bykKICB7CiAgICBpZiAocmFuayA+IDEpCiAgICAgIHsKICAgICAgICAvLyBBc2sgc3Vib3JkaW5hdGUgdG8gbW92ZSBhbGwgdGhlIHRvcCBkaXNrczoKICAgICAgICBNb25rIG1pbm9yX21vbmsocmFuayAtIDEpOwogICAgICAgIHVuc2lnbmVkIG90aGVyID0gb3RoZXJfdG93ZXIoZnJvbSwgdG8pOwogICAgICAgIG1pbm9yX21vbmsuc29sdmVfcHV6emxlKHRlbXBsZSwgZnJvbSwgb3RoZXIpOwogICAgICAgIC8vIE1vdmUgdGhlIGxhc3QgcGllY2UKICAgICAgICB0ZW1wbGUubW92ZShmcm9tLCB0byk7CiAgICAgICAgLy8gUHJvdWRseSBkcmF3IHRoZSByZXN1bHQ6CiAgICAgICAgc3RkOjpjb3V0IDw8IHRlbXBsZTsKICAgICAgICAvLyBBc2sgc3Vib3JkaW5hdGUgdG8gbW92ZSBhbGwgdGhlIHJlc3Q6CiAgICAgICAgbWlub3JfbW9uay5zb2x2ZV9wdXp6bGUodGVtcGxlLCBvdGhlciwgdG8pOyAgICAgICAgCiAgICAgIH0KICAgIGVsc2UKICAgICAgewogICAgICAgIC8vIFRoaXMgdGFzayBpcyBzaW1wbGUsIGV2ZW4gZm9yIHRoZSBsb3dsaWVzdCBtb25rOgogICAgICAgIHRlbXBsZS5tb3ZlKGZyb20sIHRvKTsKICAgICAgICAvLyBQcm91ZGx5IGRyYXcgdGhlIHJlc3VsdDoKICAgICAgICBzdGQ6OmNvdXQgPDwgdGVtcGxlOwogICAgICB9CiAgfQp9OwoKaW50IG1haW4oKQp7CiAgY29uc3QgdW5zaWduZWQgbnVtX2Rpc2tzID0gNTsKICBUZW1wbGU8bnVtX2Rpc2tzPiB0ZW1wbGU7CiAgdHJ5CiAgICB7CiAgICAgIHN0ZDo6Y291dCA8PCB0ZW1wbGU7CiAgICAgIE1vbmsgYWJib3QobnVtX2Rpc2tzKTsKICAgICAgYWJib3Quc29sdmVfcHV6emxlKHRlbXBsZSwgMCwgMSk7CiAgICAgIHRlbXBsZS5zaG93X3RvX2JyYWhtYSgpOwogICAgfQogIGNhdGNoIChFbmRPZlRoZVdvcmxkQXNXZUtub3dJdCkKICAgIHsKICAgICAgc3RkOjpjb3V0IDw8ICJCcmFobWEgaXN0IHp1ZnJpZWRlbi4gRGFzIFVuaXZlcnN1bSBoYXQgc2VpbmVuIFp3ZWNrICIKICAgICAgICAiZXJmw7xsbHQgdW5kIGthbm4gbnVuIG5ldSBlcnNjaGFmZmVuIHdlcmRlbi4gRWluZW4gc2Now7ZuZW4gVGFnIG5vY2ghXG4iOwogICAgfQp9Cg==