Merge pull request #3815

ffe9d882 speed up get_output_distribution (and precalc common case) (moneromooo-monero)

9 files changed, 182 insertions, 23 deletions

diff --git a/src/blockchain_db/blockchain_db.h b/src/blockchain_db/blockchain_db.h
index 1a23a9ada..1ed715315 100644
--- a/src/blockchain_db/blockchain_db.h
+++ b/src/blockchain_db/blockchain_db.h
@@ -1496,6 +1496,8 @@ public:
    */
   virtual std::map<uint64_t, std::tuple<uint64_t, uint64_t, uint64_t>> get_output_histogram(const std::vector<uint64_t> &amounts, bool unlocked, uint64_t recent_cutoff, uint64_t min_count) const = 0;
 
+  virtual bool get_output_distribution(uint64_t amount, uint64_t from_height, uint64_t to_height, std::vector<uint64_t> &distribution, uint64_t &base) const = 0;
+
   /**
    * @brief is BlockchainDB in read-only mode?
    *
diff --git a/src/blockchain_db/lmdb/db_lmdb.cpp b/src/blockchain_db/lmdb/db_lmdb.cpp
index 5672a34f6..5c20c8de4 100644
--- a/src/blockchain_db/lmdb/db_lmdb.cpp
+++ b/src/blockchain_db/lmdb/db_lmdb.cpp
@@ -3179,6 +3179,47 @@ std::map<uint64_t, std::tuple<uint64_t, uint64_t, uint64_t>> BlockchainLMDB::get
   return histogram;
 }
 
+bool BlockchainLMDB::get_output_distribution(uint64_t amount, uint64_t from_height, uint64_t to_height, std::vector<uint64_t> &distribution, uint64_t &base) const
+{
+  LOG_PRINT_L3("BlockchainLMDB::" << __func__);
+  check_open();
+
+  TXN_PREFIX_RDONLY();
+  RCURSOR(output_amounts);
+
+  distribution.clear();
+  const uint64_t db_height = height();
+  if (from_height >= db_height)
+    return false;
+  distribution.resize(db_height - from_height, 0);
+
+  bool fret = true;
+  MDB_val_set(k, amount);
+  MDB_val v;
+  MDB_cursor_op op = MDB_SET;
+  while (1)
+  {
+    int ret = mdb_cursor_get(m_cur_output_amounts, &k, &v, op);
+    op = MDB_NEXT_DUP;
+    if (ret == MDB_NOTFOUND)
+      break;
+    if (ret)
+      throw0(DB_ERROR("Failed to enumerate outputs"));
+    const outkey *ok = (const outkey *)v.mv_data;
+    const uint64_t height = ok->data.height;
+    if (height >= from_height)
+      distribution[height - from_height]++;
+    else
+      base++;
+    if (to_height > 0 && height > to_height)
+      break;
+  }
+
+  TXN_POSTFIX_RDONLY();
+
+  return true;
+}
+
 void BlockchainLMDB::check_hard_fork_info()
 {
 }
diff --git a/src/blockchain_db/lmdb/db_lmdb.h b/src/blockchain_db/lmdb/db_lmdb.h
index 9a20c0f1e..f1773bac8 100644
--- a/src/blockchain_db/lmdb/db_lmdb.h
+++ b/src/blockchain_db/lmdb/db_lmdb.h
@@ -293,6 +293,8 @@ public:
    */
   std::map<uint64_t, std::tuple<uint64_t, uint64_t, uint64_t>> get_output_histogram(const std::vector<uint64_t> &amounts, bool unlocked, uint64_t recent_cutoff, uint64_t min_count) const;
 
+  bool get_output_distribution(uint64_t amount, uint64_t from_height, uint64_t to_height, std::vector<uint64_t> &distribution, uint64_t &base) const;
+
 private:
   void do_resize(uint64_t size_increase=0);
 
diff --git a/src/cryptonote_core/blockchain.cpp b/src/cryptonote_core/blockchain.cpp
index 7fc20ff4a..d1ef7d6fe 100644
--- a/src/cryptonote_core/blockchain.cpp
+++ b/src/cryptonote_core/blockchain.cpp
@@ -1956,7 +1956,7 @@ void Blockchain::get_output_key_mask_unlocked(const uint64_t& amount, const uint
   unlocked = is_tx_spendtime_unlocked(m_db->get_tx_unlock_time(toi.first));
 }
 //------------------------------------------------------------------
-bool Blockchain::get_output_distribution(uint64_t amount, uint64_t from_height, uint64_t &start_height, std::vector<uint64_t> &distribution, uint64_t &base) const
+bool Blockchain::get_output_distribution(uint64_t amount, uint64_t from_height, uint64_t to_height, uint64_t &start_height, std::vector<uint64_t> &distribution, uint64_t &base) const
 {
   // rct outputs don't exist before v3
   if (amount == 0)
@@ -1977,22 +1977,7 @@ bool Blockchain::get_output_distribution(uint64_t amount, uint64_t from_height,
   if (from_height > start_height)
     start_height = from_height;
 
-  distribution.clear();
-  uint64_t db_height = m_db->height();
-  if (start_height >= db_height)
-    return false;
-  distribution.resize(db_height - start_height, 0);
-  bool r = for_all_outputs(amount, [&](uint64_t height) {
-    CHECK_AND_ASSERT_MES(height >= real_start_height && height <= db_height, false, "Height not in expected range");
-    if (height >= start_height)
-      distribution[height - start_height]++;
-    else
-      base++;
-    return true;
-  });
-  if (!r)
-    return false;
-  return true;
+  return m_db->get_output_distribution(amount, start_height, to_height, distribution, base);
 }
 //------------------------------------------------------------------
 // This function takes a list of block hashes from another node
diff --git a/src/cryptonote_core/blockchain.h b/src/cryptonote_core/blockchain.h
index 61096fb26..f58885812 100644
--- a/src/cryptonote_core/blockchain.h
+++ b/src/cryptonote_core/blockchain.h
@@ -527,12 +527,13 @@ namespace cryptonote
      * @brief gets per block distribution of outputs of a given amount
      *
      * @param amount the amount to get a ditribution for
-     * @param return-by-reference from_height the height before which we do not care about the data
+     * @param from_height the height before which we do not care about the data
+     * @param to_height the height after which we do not care about the data
      * @param return-by-reference start_height the height of the first rct output
      * @param return-by-reference distribution the start offset of the first rct output in this block (same as previous if none)
      * @param return-by-reference base how many outputs of that amount are before the stated distribution
      */
-    bool get_output_distribution(uint64_t amount, uint64_t from_height, uint64_t &start_height, std::vector<uint64_t> &distribution, uint64_t &base) const;
+    bool get_output_distribution(uint64_t amount, uint64_t from_height, uint64_t to_height, uint64_t &start_height, std::vector<uint64_t> &distribution, uint64_t &base) const;
 
     /**
      * @brief gets the global indices for outputs from a given transaction
diff --git a/src/cryptonote_core/cryptonote_core.cpp b/src/cryptonote_core/cryptonote_core.cpp
index ce75f74d8..01cd56a11 100644
--- a/src/cryptonote_core/cryptonote_core.cpp
+++ b/src/cryptonote_core/cryptonote_core.cpp
@@ -1073,9 +1073,9 @@ namespace cryptonote
     return m_blockchain_storage.get_random_rct_outs(req, res);
   }
   //-----------------------------------------------------------------------------------------------
-  bool core::get_output_distribution(uint64_t amount, uint64_t from_height, uint64_t &start_height, std::vector<uint64_t> &distribution, uint64_t &base) const
+  bool core::get_output_distribution(uint64_t amount, uint64_t from_height, uint64_t to_height, uint64_t &start_height, std::vector<uint64_t> &distribution, uint64_t &base) const
   {
-    return m_blockchain_storage.get_output_distribution(amount, from_height, start_height, distribution, base);
+    return m_blockchain_storage.get_output_distribution(amount, from_height, to_height, start_height, distribution, base);
   }
   //-----------------------------------------------------------------------------------------------
   bool core::get_tx_outputs_gindexs(const crypto::hash& tx_id, std::vector<uint64_t>& indexs) const
diff --git a/src/cryptonote_core/cryptonote_core.h b/src/cryptonote_core/cryptonote_core.h
index ff056c2a2..f3b9dddc0 100644
--- a/src/cryptonote_core/cryptonote_core.h
+++ b/src/cryptonote_core/cryptonote_core.h
@@ -576,7 +576,7 @@ namespace cryptonote
       *
       * @brief get per block distribution of outputs of a given amount
       */
-     bool get_output_distribution(uint64_t amount, uint64_t from_height, uint64_t &start_height, std::vector<uint64_t> &distribution, uint64_t &base) const;
+     bool get_output_distribution(uint64_t amount, uint64_t from_height, uint64_t to_height, uint64_t &start_height, std::vector<uint64_t> &distribution, uint64_t &base) const;
 
      /**
       * @copydoc miner::pause
diff --git a/src/rpc/core_rpc_server.cpp b/src/rpc/core_rpc_server.cpp
index 3645c494e..e28914d96 100644
--- a/src/rpc/core_rpc_server.cpp
+++ b/src/rpc/core_rpc_server.cpp
@@ -47,6 +47,7 @@ using namespace epee;
 #include "rpc/rpc_args.h"
 #include "core_rpc_server_error_codes.h"
 #include "p2p/net_node.h"
+#include "get_output_distribution_cache.h"
 #include "version.h"
 
 #undef MONERO_DEFAULT_LOG_CATEGORY
@@ -2103,9 +2104,23 @@ namespace cryptonote
           continue;
         }
 
+        // this is a slow operation, so we have precomputed caches of common cases
+        bool found = false;
+        for (const auto &slot: get_output_distribution_cache)
+        {
+          if (slot.amount == amount && slot.from_height == req.from_height && slot.to_height == req.to_height)
+          {
+            res.distributions.push_back({amount, slot.start_height, slot.distribution, slot.base});
+            found = true;
+            break;
+          }
+        }
+        if (found)
+          continue;
+
         std::vector<uint64_t> distribution;
         uint64_t start_height, base;
-        if (!m_core.get_output_distribution(amount, req.from_height, start_height, distribution, base))
+        if (!m_core.get_output_distribution(amount, req.from_height, req.to_height, start_height, distribution, base))
         {
           error_resp.code = CORE_RPC_ERROR_CODE_INTERNAL_ERROR;
           error_resp.message = "Failed to get rct distribution";
diff --git a/src/rpc/get_output_distribution_cache.h b/src/rpc/get_output_distribution_cache.h
new file mode 100644
index 000000000..6495e7d4c
--- /dev/null
+++ b/src/rpc/get_output_distribution_cache.h
@@ -0,0 +1,113 @@
+static const struct
+{
+  uint64_t amount;
+  uint64_t from_height;
+  uint64_t to_height;
+  uint64_t start_height;
+  uint64_t base;
+  std::vector<uint64_t> distribution;
+}
+get_output_distribution_cache[] =
+{
+  {
+    0,
+    1544704,
+    1546001,
+    1544704,
+    5143500,
+    {
+      5, 38, 37, 33, 39, 7, 1, 1, 5, 9, 7, 5, 17, 5, 3, 9, 3, 17, 5, 17, 1, 1, 15, 13, 3, 10, 5, 3, 34, 1, 45, 7, 
+      5, 17, 5, 22, 3, 1, 17, 16, 5, 1, 3, 43, 5, 13, 3, 23, 9, 7, 9, 13, 1, 11, 1, 17, 1, 3, 16, 11, 5, 11, 7, 7, 
+      33, 11, 7, 1, 5, 1, 21, 19, 1, 17, 1, 49, 17, 3, 3, 9, 35, 46, 46, 39, 26, 33, 21, 3, 23, 3, 9, 37, 1, 33, 11, 32, 
+      1, 13, 16, 12, 3, 21, 1, 18, 3, 19, 1, 25, 5, 3, 18, 7, 17, 5, 9, 15, 7, 7, 11, 9, 9, 17, 5, 16, 1, 3, 13, 3, 
+      5, 5, 5, 13, 5, 9, 5, 13, 3, 17, 15, 36, 13, 3, 20, 12, 6, 23, 17, 10, 22, 23, 1, 7, 21, 6, 23, 1, 3, 19, 13, 1, 
+      3, 43, 35, 13, 1, 31, 7, 3, 17, 1, 15, 5, 11, 15, 24, 1, 18, 13, 5, 15, 1, 29, 3, 3, 13, 3, 15, 7, 17, 3, 1, 1, 
+      17, 1, 1, 45, 39, 27, 45, 46, 34, 7, 3, 3, 9, 3, 3, 11, 7, 5, 9, 25, 19, 3, 33, 1, 5, 17, 1, 45, 4, 1, 45, 11, 
+      44, 32, 3, 1, 3, 7, 17, 15, 5, 45, 35, 41, 1, 35, 3, 3, 19, 1, 9, 17, 29, 29, 3, 1, 13, 1, 3, 47, 21, 13, 7, 1, 
+      7, 5, 1, 11, 1, 40, 9, 7, 3, 3, 13, 25, 1, 47, 5, 7, 3, 7, 31, 40, 34, 6, 3, 15, 3, 31, 5, 13, 27, 9, 12, 21, 
+      3, 1, 19, 1, 19, 5, 47, 49, 47, 42, 50, 34, 29, 23, 1, 5, 9, 16, 11, 7, 1, 19, 7, 5, 1, 15, 1, 1, 9, 13, 9, 5, 
+      27, 3, 3, 29, 1, 33, 3, 9, 5, 35, 5, 1, 17, 7, 3, 39, 3, 28, 19, 1, 1, 9, 1, 3, 27, 1, 37, 3, 1, 1, 16, 3, 
+      25, 11, 5, 3, 33, 45, 17, 11, 7, 22, 9, 1, 5, 5, 5, 15, 1, 15, 9, 7, 11, 13, 37, 49, 46, 38, 11, 1, 25, 1, 13, 18, 
+      3, 7, 39, 3, 37, 19, 35, 3, 1, 3, 19, 1, 3, 15, 21, 3, 27, 1, 45, 48, 1, 13, 29, 9, 1, 1, 46, 43, 5, 15, 3, 7, 
+      29, 26, 5, 5, 21, 37, 17, 21, 3, 13, 1, 5, 1, 17, 5, 31, 13, 1, 11, 3, 46, 9, 3, 7, 1, 1, 41, 1, 21, 1, 5, 12, 
+      7, 13, 9, 25, 1, 47, 47, 48, 48, 48, 48, 48, 47, 48, 45, 45, 33, 52, 50, 46, 45, 47, 35, 41, 38, 35, 42, 38, 34, 41, 39, 35, 
+      51, 51, 45, 43, 49, 52, 53, 45, 42, 46, 37, 53, 49, 41, 46, 49, 46, 47, 48, 37, 41, 33, 43, 38, 15, 3, 3, 27, 11, 5, 23, 13, 
+      1, 1, 37, 3, 15, 3, 30, 13, 3, 45, 12, 3, 5, 11, 1, 1, 21, 9, 11, 19, 1, 1, 1, 25, 5, 21, 3, 1, 32, 44, 3, 33, 
+      11, 7, 5, 23, 1, 37, 47, 48, 48, 48, 48, 48, 48, 46, 47, 47, 50, 45, 49, 50, 46, 47, 49, 45, 51, 49, 50, 49, 49, 46, 47, 48, 
+      46, 48, 46, 50, 46, 43, 46, 46, 48, 47, 46, 47, 45, 49, 46, 43, 50, 45, 45, 49, 45, 48, 45, 49, 48, 45, 45, 51, 45, 51, 45, 46, 
+      52, 45, 45, 51, 51, 52, 44, 45, 52, 50, 50, 46, 47, 51, 51, 46, 47, 47, 47, 50, 47, 51, 48, 49, 51, 50, 48, 48, 48, 50, 49, 49, 
+      52, 52, 49, 50, 49, 49, 49, 51, 52, 49, 52, 50, 49, 47, 29, 15, 39, 17, 31, 5, 40, 5, 18, 23, 25, 7, 35, 26, 5, 31, 49, 22, 
+      3, 17, 7, 49, 7, 49, 47, 12, 44, 46, 36, 15, 3, 1, 47, 13, 35, 40, 5, 21, 19, 39, 21, 33, 31, 29, 1, 1, 37, 1, 15, 47, 
+      7, 7, 47, 41, 13, 3, 47, 31, 9, 33, 13, 43, 29, 5, 1, 9, 33, 7, 27, 15, 15, 25, 5, 43, 22, 31, 7, 1, 47, 1, 15, 27, 
+      3, 27, 45, 15, 1, 36, 17, 1, 23, 39, 38, 45, 7, 7, 19, 7, 11, 47, 33, 16, 3, 45, 45, 45, 9, 27, 3, 3, 21, 3, 7, 21, 
+      7, 3, 43, 1, 17, 1, 45, 37, 46, 5, 5, 13, 46, 40, 48, 48, 45, 34, 1, 46, 19, 25, 9, 7, 47, 23, 37, 31, 3, 25, 13, 46, 
+      31, 25, 5, 46, 35, 52, 11, 23, 27, 4, 15, 11, 11, 11, 9, 34, 7, 9, 15, 34, 9, 27, 37, 28, 25, 45, 13, 30, 5, 25, 15, 7, 
+      3, 19, 27, 1, 7, 11, 1, 32, 3, 45, 11, 9, 21, 25, 9, 13, 13, 1, 7, 1, 33, 11, 5, 3, 3, 27, 27, 5, 3, 37, 17, 17, 
+      3, 7, 5, 13, 1, 3, 44, 45, 26, 25, 1, 13, 3, 13, 3, 11, 1, 11, 7, 45, 3, 3, 1, 43, 1, 19, 3, 1, 15, 5, 39, 7, 
+      7, 1, 9, 1, 11, 19, 3, 35, 29, 7, 15, 11, 40, 7, 44, 38, 34, 7, 9, 7, 1, 27, 1, 9, 5, 45, 1, 21, 3, 1, 5, 9, 
+      3, 21, 23, 33, 3, 1, 7, 3, 3, 7, 41, 9, 7, 1, 5, 31, 9, 7, 1, 1, 11, 41, 51, 20, 9, 47, 39, 17, 9, 35, 1, 41, 
+      1, 19, 1, 19, 15, 1, 13, 5, 23, 15, 9, 15, 17, 1, 15, 27, 33, 31, 29, 7, 13, 1, 5, 45, 5, 1, 1, 11, 1, 13, 3, 7, 
+      9, 1, 13, 39, 3, 33, 5, 3, 7, 7, 5, 29, 11, 1, 7, 1, 15, 3, 13, 3, 15, 3, 3, 1, 5, 1, 9, 1, 44, 49, 24, 25, 
+      1, 1, 34, 22, 7, 5, 5, 5, 10, 9, 13, 3, 9, 1, 9, 19, 7, 43, 48, 7, 11, 7, 3, 3, 7, 21, 1, 1, 3, 3, 11, 31, 
+      1, 1, 13, 22, 23, 7, 27, 9, 3, 3, 21, 1, 35, 21, 9, 11, 13, 39, 1, 3, 7, 23, 3, 28, 3, 45, 47, 38, 32, 37, 34, 1, 
+      23, 3, 3, 1, 19, 19, 1, 5, 13, 1, 5, 11, 38, 3, 1, 36, 13, 1, 1, 23, 5, 17, 11, 1, 13, 1, 3, 7, 11, 3, 33, 7, 
+      19, 5, 5, 1, 1, 3, 5, 41, 1, 3, 25, 1, 7, 7, 9, 3, 11, 3, 13, 5, 7, 1, 3, 9, 1, 1, 43, 47, 47, 47, 17, 7, 
+      17, 3, 19, 1, 9, 9, 33, 22, 1, 25, 1, 3, 3, 32, 5, 1, 23, 9, 5, 1, 31, 5, 9, 1, 3, 7, 19, 1, 12, 11, 5, 1, 
+      1, 9, 25, 15, 15, 13, 5, 3, 15, 1, 17, 1, 1, 5, 5, 41, 11, 15, 7, 3, 21, 21, 35, 22, 46, 35, 3, 27, 5, 3, 45, 22, 
+      27, 1, 19, 9, 1, 25, 1, 29, 3, 5, 25, 17, 27, 5, 19, 5, 25, 7, 19, 1, 9, 21, 3, 7, 29, 27, 17, 3, 3, 15, 7, 19, 
+      5, 25, 1, 23, 45, 4, 31, 1, 37, 14, 29, 3, 29, 1, 23, 29, 19, 11, 1, 13, 13, 9, 1, 25, 1, 33, 1, 37, 37, 23, 7, 21, 
+      7, 3, 13, 7, 3, 7, 21, 11, 9, 1, 31, 3, 1, 7, 39, 46, 3, 30, 
+    },
+  },
+  {
+    0,
+    1562704,
+    1564001,
+    1562704,
+    5521986,
+    {
+      35, 45, 23, 3, 44, 47, 44, 3, 17, 35, 7, 11, 7, 29, 43, 27, 11, 7, 5, 31, 13, 9, 45, 45, 7, 42, 17, 15, 19, 11, 45, 19, 
+      45, 46, 45, 46, 32, 34, 43, 34, 46, 47, 45, 30, 17, 45, 46, 36, 35, 38, 19, 9, 23, 17, 3, 19, 31, 41, 35, 24, 15, 45, 15, 5, 
+      11, 5, 19, 11, 11, 7, 15, 19, 45, 34, 7, 7, 29, 1, 9, 36, 7, 44, 45, 33, 25, 8, 17, 7, 44, 43, 48, 45, 42, 46, 40, 44, 
+      1, 43, 45, 46, 46, 35, 19, 19, 23, 5, 13, 19, 7, 16, 9, 3, 25, 34, 3, 27, 9, 39, 3, 43, 21, 1, 45, 45, 39, 25, 23, 13, 
+      39, 39, 3, 45, 43, 46, 44, 40, 39, 33, 45, 47, 38, 45, 45, 39, 47, 47, 45, 46, 35, 45, 43, 47, 45, 40, 34, 42, 42, 48, 49, 47, 
+      47, 48, 47, 45, 43, 48, 37, 48, 41, 45, 48, 34, 42, 44, 9, 19, 27, 1, 47, 47, 43, 25, 29, 5, 5, 21, 39, 35, 43, 37, 13, 45, 
+      25, 31, 26, 47, 45, 23, 23, 39, 32, 25, 44, 47, 35, 47, 15, 17, 7, 9, 5, 35, 31, 3, 45, 47, 46, 13, 17, 48, 45, 9, 13, 45, 
+      45, 31, 1, 53, 44, 46, 39, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 47, 47, 47, 47, 47, 47, 47, 47, 53, 49, 45, 45, 50, 
+      50, 27, 43, 46, 47, 46, 45, 48, 36, 42, 42, 46, 45, 47, 41, 45, 43, 47, 38, 48, 47, 33, 11, 45, 46, 34, 42, 32, 3, 45, 37, 45, 
+      15, 3, 45, 29, 31, 9, 5, 3, 27, 5, 21, 25, 7, 15, 46, 34, 5, 3, 17, 3, 9, 13, 7, 11, 3, 1, 34, 13, 7, 45, 33, 26, 
+      9, 5, 9, 41, 43, 34, 3, 35, 3, 17, 37, 11, 17, 3, 15, 27, 15, 45, 46, 13, 26, 16, 11, 7, 5, 45, 38, 45, 45, 22, 44, 44, 
+      43, 6, 11, 35, 15, 44, 17, 27, 13, 3, 40, 5, 9, 7, 35, 19, 5, 5, 1, 28, 33, 15, 45, 5, 29, 3, 31, 12, 5, 32, 24, 3, 
+      23, 13, 47, 45, 42, 46, 39, 21, 21, 1, 44, 44, 47, 41, 5, 1, 11, 36, 20, 5, 45, 39, 45, 45, 44, 45, 32, 22, 40, 11, 38, 1, 
+      45, 46, 37, 9, 23, 9, 15, 44, 7, 16, 38, 46, 11, 14, 24, 19, 19, 7, 26, 25, 45, 37, 17, 1, 35, 1, 3, 28, 3, 11, 22, 13, 
+      3, 1, 7, 38, 5, 3, 1, 26, 1, 3, 43, 44, 46, 45, 21, 11, 1, 44, 27, 1, 11, 26, 10, 44, 45, 45, 45, 47, 47, 45, 48, 45, 
+      38, 9, 5, 44, 46, 27, 3, 12, 1, 11, 3, 44, 43, 1, 5, 2, 46, 17, 13, 19, 1, 12, 7, 23, 1, 17, 6, 13, 3, 5, 27, 7, 
+      46, 36, 19, 25, 1, 1, 3, 8, 15, 3, 45, 45, 45, 37, 6, 15, 3, 5, 38, 14, 41, 1, 13, 45, 45, 39, 44, 29, 43, 48, 51, 50, 
+      37, 5, 17, 46, 47, 31, 5, 42, 49, 38, 39, 24, 7, 11, 44, 35, 21, 6, 15, 5, 47, 13, 28, 45, 34, 27, 24, 15, 35, 13, 7, 25, 
+      43, 13, 14, 5, 3, 5, 46, 45, 45, 35, 5, 21, 28, 3, 13, 4, 30, 19, 45, 45, 40, 37, 5, 40, 17, 9, 3, 9, 13, 4, 17, 33, 
+      44, 39, 17, 45, 28, 5, 11, 45, 19, 45, 21, 44, 31, 43, 49, 48, 15, 3, 1, 44, 45, 43, 11, 1, 1, 27, 43, 45, 39, 3, 1, 3, 
+      5, 31, 1, 43, 23, 19, 7, 5, 45, 31, 11, 7, 3, 9, 5, 7, 13, 43, 47, 45, 46, 47, 14, 3, 25, 45, 7, 17, 32, 21, 3, 17, 
+      5, 11, 31, 40, 45, 20, 45, 45, 32, 38, 47, 38, 45, 41, 49, 30, 45, 5, 36, 31, 22, 3, 46, 45, 13, 21, 23, 5, 46, 45, 33, 19, 
+      25, 1, 7, 13, 5, 44, 23, 29, 23, 24, 7, 5, 37, 13, 29, 13, 7, 17, 7, 43, 3, 21, 7, 44, 1, 19, 15, 9, 34, 43, 26, 3, 
+      17, 5, 6, 5, 7, 3, 33, 35, 43, 41, 48, 47, 30, 45, 19, 7, 5, 33, 11, 34, 25, 1, 21, 11, 29, 7, 1, 4, 5, 10, 14, 3, 
+      44, 11, 47, 45, 33, 3, 9, 7, 40, 23, 9, 1, 3, 1, 7, 5, 9, 9, 6, 11, 45, 41, 45, 19, 5, 11, 10, 39, 9, 19, 3, 11, 
+      43, 42, 1, 13, 35, 5, 32, 7, 5, 5, 43, 37, 3, 32, 17, 3, 23, 1, 13, 45, 17, 1, 21, 45, 43, 46, 49, 47, 45, 30, 9, 31, 
+      19, 42, 19, 44, 17, 14, 19, 25, 1, 7, 5, 45, 19, 13, 7, 3, 1, 1, 9, 21, 37, 9, 11, 1, 3, 37, 27, 13, 5, 21, 33, 3, 
+      27, 9, 27, 1, 39, 1, 46, 21, 10, 13, 21, 40, 22, 35, 41, 9, 33, 3, 17, 8, 45, 46, 42, 46, 47, 47, 47, 48, 48, 47, 43, 48, 
+      37, 39, 50, 35, 3, 40, 45, 40, 46, 36, 34, 28, 9, 9, 37, 9, 5, 7, 13, 31, 1, 7, 3, 3, 44, 45, 25, 15, 1, 21, 43, 25, 
+      1, 38, 34, 42, 31, 23, 33, 35, 37, 20, 7, 15, 3, 7, 7, 27, 45, 45, 48, 47, 45, 44, 47, 23, 25, 36, 11, 3, 18, 24, 27, 13, 
+      41, 13, 5, 5, 7, 19, 15, 7, 5, 14, 45, 45, 37, 1, 5, 17, 21, 41, 17, 37, 53, 41, 45, 45, 45, 45, 45, 45, 45, 45, 43, 47, 
+      47, 48, 53, 47, 47, 47, 49, 27, 45, 47, 47, 47, 47, 45, 45, 45, 47, 43, 48, 34, 34, 43, 46, 15, 37, 21, 5, 27, 11, 1, 9, 7, 
+      19, 15, 1, 1, 19, 3, 36, 27, 29, 13, 21, 9, 17, 5, 16, 45, 23, 34, 3, 1, 7, 25, 28, 13, 29, 15, 11, 19, 17, 1, 27, 23, 
+      31, 19, 41, 41, 40, 47, 28, 31, 26, 26, 36, 17, 5, 1, 23, 1, 45, 34, 49, 51, 34, 43, 37, 5, 41, 15, 5, 21, 1, 7, 9, 19, 
+      5, 11, 39, 19, 45, 45, 38, 17, 9, 1, 15, 11, 5, 13, 47, 46, 48, 45, 19, 32, 7, 19, 5, 7, 23, 29, 5, 45, 41, 37, 1, 5, 
+      27, 5, 5, 7, 19, 9, 1, 35, 48, 38, 38, 39, 42, 43, 21, 23, 43, 41, 7, 3, 7, 13, 1, 46, 47, 46, 23, 46, 45, 25, 7, 9, 
+      21, 7, 41, 13, 20, 1, 21, 15, 37, 5, 40, 45, 45, 5, 45, 46, 15, 33, 46, 12, 13, 7, 24, 7, 5, 30, 7, 46, 13, 8, 44, 35, 
+      45, 33, 40, 36, 47, 47, 29, 43, 36, 43, 45, 42, 36, 19, 7, 7, 43, 3, 44, 25, 48, 29, 11, 45, 30, 1, 17, 13, 25, 1, 48, 45, 
+      45, 45, 44, 49, 37, 9, 21, 17, 15, 7, 15, 25, 1, 1, 9, 43, 33, 11, 3, 29, 45, 45, 9, 7, 7, 27, 47, 45, 47, 48, 45, 47, 
+      26, 1, 43, 15, 45, 17, 1, 5, 35, 31, 9, 3, 9, 19, 9, 21, 43, 5, 27, 1, 5, 9, 4, 34, 19, 3, 7, 11, 45, 46, 45, 45, 
+      46, 47, 47, 44, 45, 43, 27, 9, 17, 15, 19, 44, 45, 46, 47, 47, 45, 45, 
+    }
+  }
+};
+