/tmp/solutions/build/predecessor_problem-main.cpp:
    1|       |#include <common.h>
    2|       |prelude;
    3|       |
    4|       |namespace {
    5|       |
    6|       |u64 root;
    7|       |u64 lv18[39];
    8|       |u64 lv12[2442];
    9|       |u64 leaf[156250];
   10|       |
   11|  1.26M|void set(u32 x) {
   12|  1.26M|  leaf[x >> 6] |= 1ull << (x & 63);
   13|  1.26M|  lv12[x >> 12] |= 1ull << ((x >> 6) & 63);
   14|  1.26M|  lv18[x >> 18] |= 1ull << ((x >> 12) & 63);
   15|  1.26M|  root |= 1ull << (x >> 18);
   16|  1.26M|}
   17|       |
   18|  1.76M|void unset(u32 x) {
   19|  1.76M|  if (!(leaf[x >> 6] &= ~(1ull << (x & 63))))
  ------------------
  |  Branch (19:7): [True: 0.25%, False: 99.75%]
  ------------------
   20|  4.36k|    if (!(lv12[x >> 12] &= ~(1ull << ((x >> 6) & 63))))
  ------------------
  |  Branch (20:9): [True: 0.07%, False: 99.93%]
  ------------------
   21|      3|      if (!(lv18[x >> 18] &= ~(1ull << ((x >> 12) & 63))))
  ------------------
  |  Branch (21:11): [True: 0.00%, False: 100.00%]
  ------------------
   22|      0|        root &= ~(1ull << (x >> 18));
   23|  1.76M|}
   24|       |
   25|  2.44M|bool get(u32 x) { return leaf[x >> 6] & (1ull << (x & 63)); }
   26|       |
   27|  2.77M|u32 nxt(u32 x) {
   28|  2.77M|  if (u64 tmp = leaf[x >> 6] & (-1ull << (x & 63)); !tmp) {
  ------------------
  |  Branch (28:53): [True: 60.66%, False: 39.34%]
  ------------------
   29|  1.68M|    if (u64 tmp = lv12[x >> 12] & (-2ull << ((x >> 6) & 63)); !tmp) {
  ------------------
  |  Branch (29:63): [True: 99.31%, False: 0.69%]
  ------------------
   30|  1.66M|      if (u64 tmp = lv18[x >> 18] & (-2ull << ((x >> 12) & 63)); !tmp) {
  ------------------
  |  Branch (30:66): [True: 95.22%, False: 4.78%]
  ------------------
   31|  1.58M|        if (u64 tmp = root & (-2ull << (x >> 18)); !tmp) {
  ------------------
  |  Branch (31:52): [True: 50.84%, False: 49.16%]
  ------------------
   32|   808k|          return -1;
   33|   808k|        } else {
   34|   781k|          u32 ans = __builtin_ctzll(tmp);
   35|   781k|          ans = ans << 6 | __builtin_ctzll(lv18[ans]);
   36|   781k|          ans = ans << 6 | __builtin_ctzll(lv12[ans]);
   37|   781k|          ans = ans << 6 | __builtin_ctzll(leaf[ans]);
   38|   781k|          return ans;
   39|   781k|        }
   40|  1.58M|      } else {
   41|  79.7k|        u32 ans = (x >> 18) << 6 | __builtin_ctzll(tmp);
   42|  79.7k|        ans = ans << 6 | __builtin_ctzll(lv12[ans]);
   43|  79.7k|        ans = ans << 6 | __builtin_ctzll(leaf[ans]);
   44|  79.7k|        return ans;
   45|  79.7k|      }
   46|  1.66M|    } else {
   47|  11.6k|      u32 ans = (x >> 12) << 6 | __builtin_ctzll(tmp);
   48|  11.6k|      ans = ans << 6 | __builtin_ctzll(leaf[ans]);
   49|  11.6k|      return ans;
   50|  11.6k|    }
   51|  1.68M|  } else {
   52|  1.09M|    u32 ans = (x >> 6) << 6 | __builtin_ctzll(tmp);
   53|  1.09M|    return ans;
   54|  1.09M|  }
   55|  2.77M|}
   56|       |
   57|  2.77M|u32 pre(u32 x) {
   58|  2.77M|  if (u64 tmp = leaf[x >> 6] & ~(-2ull << (x & 63)); !tmp) {
  ------------------
  |  Branch (58:54): [True: 60.68%, False: 39.32%]
  ------------------
   59|  1.68M|    if (u64 tmp = lv12[x >> 12] & ~(-1ull << ((x >> 6) & 63)); !tmp) {
  ------------------
  |  Branch (59:64): [True: 99.34%, False: 0.66%]
  ------------------
   60|  1.66M|      if (u64 tmp = lv18[x >> 18] & ~(-1ull << ((x >> 12) & 63)); !tmp) {
  ------------------
  |  Branch (60:67): [True: 93.95%, False: 6.05%]
  ------------------
   61|  1.56M|        if (u64 tmp = root & ~(-1ull << (x >> 18)); !tmp) {
  ------------------
  |  Branch (61:53): [True: 49.81%, False: 50.19%]
  ------------------
   62|   781k|          return -1;
   63|   787k|        } else {
   64|   787k|          u32 ans = 63 - __builtin_clzll(tmp);
   65|   787k|          ans = ans << 6 | 63 - __builtin_clzll(lv18[ans]);
   66|   787k|          ans = ans << 6 | 63 - __builtin_clzll(lv12[ans]);
   67|   787k|          ans = ans << 6 | 63 - __builtin_clzll(leaf[ans]);
   68|   787k|          return ans;
   69|   787k|        }
   70|  1.56M|      } else {
   71|   100k|        u32 ans = (x >> 18) << 6 | 63 - __builtin_clzll(tmp);
   72|   100k|        ans = ans << 6 | 63 - __builtin_clzll(lv12[ans]);
   73|   100k|        ans = ans << 6 | 63 - __builtin_clzll(leaf[ans]);
   74|   100k|        return ans;
   75|   100k|      }
   76|  1.66M|    } else {
   77|  11.0k|      u32 ans = (x >> 12) << 6 | 63 - __builtin_clzll(tmp);
   78|  11.0k|      ans = ans << 6 | 63 - __builtin_clzll(leaf[ans]);
   79|  11.0k|      return ans;
   80|  11.0k|    }
   81|  1.68M|  } else {
   82|  1.08M|    u32 ans = (x >> 6) << 6 | 63 - __builtin_clzll(tmp);
   83|  1.08M|    return ans;
   84|  1.08M|  }
   85|  2.77M|}
   86|       |
   87|       |} // namespace
   88|       |
   89|     22|int main() {
   90|     22|  rd rd;
   91|     22|  wt wt;
   92|     22|  int n = rd.uh();
   93|     22|  int q = rd.uh();
   94|     22|#ifdef LOCAL
   95|     22|  root = 0;
   96|     22|  std::memset(lv18, 0, sizeof(lv18));
   97|     22|  std::memset(lv12, 0, sizeof(lv12));
   98|     22|  std::memset(leaf, 0, sizeof(leaf));
   99|     22|#endif
  100|     22|  int i = 0;
  101|  1.56M|  for (; i + 64 < n; i += 64) {
                                   ^1.56M
  ------------------
  |  Branch (101:10): [True: 100.00%, False: 0.00%]
  ------------------
  102|  1.56M|    u32 a = _mm256_movemask_epi8(_mm256_cmpeq_epi8(
  103|  1.56M|        _mm256_loadu_si256(reinterpret_cast<const __m256i_u *>(rd.p + i)),
  104|  1.56M|        _mm256_set1_epi8('1')));
  105|  1.56M|    u32 b = _mm256_movemask_epi8(_mm256_cmpeq_epi8(
  106|  1.56M|        _mm256_loadu_si256(reinterpret_cast<const __m256i_u *>(rd.p + i + 32)),
  107|  1.56M|        _mm256_set1_epi8('1')));
  108|  1.56M|    leaf[i >> 6] = a | u64(b) << 32;
  109|  1.56M|  }
  110|  1.17k|  for (; i < n; ++i) leaf[i >> 6] |= u64(rd.p[i] - '0') << (i & 63);
                              ^1.15k^1.15k
  ------------------
  |  Branch (110:10): [True: 98.13%, False: 1.87%]
  ------------------
  111|  1.56M|  for (int i = 0; i <= (n - 1) / 64; ++i)
                                                   ^1.56M
  ------------------
  |  Branch (111:19): [True: 100.00%, False: 0.00%]
  ------------------
  112|  1.56M|    lv12[i >> 6] |= u64(!!leaf[i]) << (i & 63);
  113|  24.4k|  for (int i = 0; i <= (n - 1) / 64 / 64; ++i)
                                                        ^24.4k
  ------------------
  |  Branch (113:19): [True: 99.91%, False: 0.09%]
  ------------------
  114|  24.4k|    lv18[i >> 6] |= u64(!!lv12[i]) << (i & 63);
  115|    424|  for (int i = 0; i <= (n - 1) / 64 / 64 / 64; ++i)
                                                             ^402
  ------------------
  |  Branch (115:19): [True: 94.81%, False: 5.19%]
  ------------------
  116|    402|    root |= u64(!!lv18[i]) << (i & 63);
  117|     22|  rd.p += n + 1;
  118|  11.0M|  while (q--) {
  ------------------
  |  Branch (118:10): [True: 100.00%, False: 0.00%]
  ------------------
  119|  11.0M|    let t = rd.u1();
  120|  11.0M|    let k = rd.uh();
  121|  11.0M|    if (t == 0) {
  ------------------
  |  Branch (121:9): [True: 11.48%, False: 88.52%]
  ------------------
  122|  1.26M|      set(k);
  123|  1.26M|    }
  124|  11.0M|    if (t == 1) {
  ------------------
  |  Branch (124:9): [True: 16.06%, False: 83.94%]
  ------------------
  125|  1.76M|      unset(k);
  126|  1.76M|    }
  127|  11.0M|    if (t == 2) {
  ------------------
  |  Branch (127:9): [True: 22.15%, False: 77.85%]
  ------------------
  128|  2.44M|      let x = get(k);
  129|  2.44M|      wt.uw(x);
  130|  2.44M|    }
  131|  11.0M|    if (t == 3) {
  ------------------
  |  Branch (131:9): [True: 25.16%, False: 74.84%]
  ------------------
  132|  2.77M|      let x = nxt(k);
  133|  2.77M|      if (~x) {
  ------------------
  |  Branch (133:11): [True: 70.84%, False: 29.16%]
  ------------------
  134|  1.96M|        wt.uw(x);
  135|  1.96M|      } else {
  136|   808k|        wt.puts(" -1", 3);
  137|   808k|      }
  138|  2.77M|    }
  139|  11.0M|    if (t == 4) {
  ------------------
  |  Branch (139:9): [True: 25.15%, False: 74.85%]
  ------------------
  140|  2.77M|      let x = pre(k);
  141|  2.77M|      if (~x) {
  ------------------
  |  Branch (141:11): [True: 71.79%, False: 28.21%]
  ------------------
  142|  1.98M|        wt.uw(x);
  143|  1.98M|      } else {
  144|   781k|        wt.puts(" -1", 3);
  145|   781k|      }
  146|  2.77M|    }
  147|  11.0M|  }
  148|     22|  return 0;
  149|     22|}