text:
#pragma once
#include <bits/stdc++.h>
using namespace std;

// Fischer Heun Structure supporting range maximum queries on a static array
// Indices are 0-indexed and ranges are inclusive
// Template Arguments:
//   T: the type of each element
//   Cmp: the comparator to compare two values,
//       convention is same as std::priority_queue in STL
//     Required Functions:
//       operator (a, b): returns true if and only if a compares less than b
//   mask_t: the type to store a bitmask, should have around log(N) bits
// Constructor Arguments:
//   A: a vector of type T of the values in the array
//   cmp: an instance of the Cmp struct
// Functions:
//   queryInd(l, r): returns the index of the maximum element in
//     the subarray [l, r], breaking ties by selecting the first such index;
//     the last such index can be obtained by using less_equal or greater_equal
//     as the Cmp struct
//   query(l, r): returns the maximum element (based on the comparator) in
//     the subarray [l, r]
// In practice, the constructor has a moderate constant and is significantly
//   faster than sparse table's constructor, query has a moderate constant and
//   is slightly slower than sparse table's query
// Time Complexity:
//   constructor: O(N + N / B log (N / B)), where B is
//     the number of bits in mask_t
//   queryInd, query: O(1) assuming bitshift for mask_t is O(1)
// Memory Complexity: O(N + N / B log (N / B)) assuming mask_t is O(1) memory
// Tested:
//   Fuzz and Stress Tested
//   https://dmoj.ca/problem/ncco3d2p1
//   https://www.spoj.com/problems/RMQSQ/
//   https://judge.yosupo.jp/problem/staticrmq
template <class T, class Cmp = less<T>, class mask_t = uint32_t>
struct FischerHeunStructure {
  static_assert(is_integral<mask_t>::value, "mask_t must be integral");
  static_assert(is_unsigned<mask_t>::value, "mask_t must be unsigned");
  static constexpr const int B = __lg(numeric_limits<mask_t>::max()) + 1;
  int N, M; vector<T> A; vector<mask_t> mask; vector<vector<int>> ST; Cmp cmp;
  int cmpInd(int i, int j) { return cmp(A[i], A[j]) ? j : i; }
  int small(int r, int sz = B) {
    return r - __lg(sz == B ? mask[r] : mask[r] & ((mask_t(1) << sz) - 1));
  }
  FischerHeunStructure(vector<T> A, Cmp cmp = Cmp())
      : N(A.size()), M(N / B), A(move(A)), mask(N),
        ST(M == 0 ? 0 : __lg(M) + 1, vector<int>(M)), cmp(cmp) {
    mask_t k = 0; for (int i = 0; i < N; mask[i++] = k |= 1)
      for (k <<= 1; k && cmpInd(i - __lg(k & -k), i) == i;) k ^= k & -k;
    for (int i = 0; i < M; i++) ST[0][i] = small(B * (i + 1) - 1);
    for (int i = 0; i < int(ST.size()) - 1; i++) for (int j = 0; j < M; j++)
      ST[i + 1][j] = cmpInd(ST[i][j], ST[i][min(j + (1 << i), M - 1)]);
  }
  int queryInd(int l, int r) {
    if (r - l + 1 <= B) return small(r, r - l + 1);
    int ql = small(l + B - 1), qr = small(r); l = l / B + 1; r = r / B - 1;
    if (l <= r) {
      int i = __lg(r - l + 1);
      ql = cmpInd(ql, cmpInd(ST[i][l], ST[i][r - (1 << i) + 1]));
    }
    return cmpInd(ql, qr);
  }
  T query(int l, int r) { return A[queryInd(l, r)]; }
};


text:
#pragma once
#include <bits/stdc++.h>
#include "WaveletMatrixAggregation.h"
using namespace std;

// Wavelet Matrix supporting 2D aggregation queries where the data can change,
//   and the indices and the keys that are updated are known beforehand
// Indices are 0-indexed and ranges are inclusive
// Queries bounded by 3 indices require a commutative operation, while queries
//   bounded by 4 indices also requires the data to be invertible
// Indices are 0-indexed and ranges are inclusive
// Template Arguments:
//   T: the type of the element of the array
//   R: struct supporting point updates and range queries on indices
//     Required Fields:
//       Data: the data type
//       Lazy: the lazy type
//     Required Functions:
//       static qdef(): returns the query default value
//       static merge(l, r): returns the values l of type Data merged with
//         r of type Data, must be associative and commutative
//       static applyLazy(l, r): returns the value r of type Lazy applied to
//         l of type Data
//       constructor(A): takes a vector A of type Data with the initial
//         value of each index
//       update(i, val): updates the index i with the value val
//       query(l, r): queries the range [l, r]
//     Sample Struct: supporting point increments updates and range sum queries
//       struct R {
//         using Data = int;
//         using Lazy = int;
//         static Data qdef() { return 0; }
//         static Data merge(const Data &l, const Data &r) { return l + r; }
//         static Data applyLazy(const Data &l, const Lazy &r) {
//           return l + r;
//         }
//         FenwickTree1D<Data> FT;
//         R(vector<Data> A) : FT(move(A)) {}
//         void update(int i, const Lazy &val) { FT.update(i, val); }
//         Data query(int l, int r) { return FT.query(l, r); }
//       };
//   Cmp: the comparator to compare two elements of type T
//     Required Functions:
//       operator (a, b): returns true if and only if a compares less than b
// Constructor Arguments:
//   A: a vector of type T containing the initial keys of the array
//   D: a vector of type R::Data containing the initial data of the array
//   updates: a vector of vectors of type T containing the sequence of updates
//     to each index in the order they are updated
//   cmp: an instance of the Cmp struct
// Functions:
//   updateToNextKey(i): updates the ith key to the next key in the update
//     sequence
//   update(i, v): updates the ith data with the lazy value v
//   query(l, r, hi): returns the aggregate value of the data associated with
//     all elements with a key less than or equal to hi (using the comparator)
//     in the range [l, r]
//   query(l, r, lo, hi): returns the aggregate value of the data associated
//     with all elements with a key of not less than lo and not greater than hi
//     (using the comparator) in the range [l, r]
//   bsearch(l, r, f): over all keys in the array, finds the first key k such
//     that query(l, r, k) returns true
// In practice, has a small constant, faster than using an
//   Offline or Online 2D Sparse Fenwick Tree or Segment Tree
// Time Complexity:
//   constructor: O((N + K + C) log N + K) where C is the time complexity of
//     R's constructor for K total updates
//   updateToNextKey: O(U log (N + K)) where U is the time complexity of R's
//     update function for K total updates
//   update: O(U log (N + K)) where U is the time complexity of R's update
//     function for K total updates
//   query, bsearch: O(Q log N) where Q is the time complexity of
//     R's query function for K total updates
// Memory Complexity: O(N + K + ((N + K) log (N + K)) / 64 + M log (N + K))
//   where M is the memory complexity of R for K total updates
// Tested:
//   https://dmoj.ca/problem/oly19practice4
template <class T, class R, class Cmp = less<T>>
struct WaveletMatrixAggregationOfflineUpdates {
  using Data = typename R::Data; using Lazy = typename R::Lazy;
  vector<int> cur; vector<Data> D; WaveletMatrixAggregation<T, R, Cmp> wm;
  WaveletMatrixAggregation<T, R, Cmp> init(
      const vector<T> &A, const vector<Data> &D,
      const vector<vector<T>> &updates, Cmp cmp) {
    assert(A.size() == D.size()); assert(A.size() == updates.size());
    int N = A.size();
    for (int i = 0; i < N; i++) cur[i + 1] = updates[i].size() + 1;
    partial_sum(cur.begin(), cur.end(), cur.begin());
    vector<T> ret; ret.reserve(cur[N]); for (int i = 0; i < N; i++) {
      ret.push_back(A[i]);
      ret.insert(ret.end(), updates[i].begin(), updates[i].end());
    }
    vector<Data> temp(ret.size(), R::qdef());
    for (int i = 0; i < N; i++) temp[cur[i]] = D[i];
    return WaveletMatrixAggregation<T, R, Cmp>(move(ret), temp, cmp);
  }
  WaveletMatrixAggregationOfflineUpdates(
      const vector<T> &A, const vector<Data> &D,
      const vector<vector<T>> &updates, Cmp cmp = Cmp())
      : cur(A.size() + 1, 0), D(D), wm(init(A, D, updates, cmp)) {}
  void updateToNextKey(int i) {
    wm.update(cur[i], R::qdef()); wm.update(++cur[i], D[i]);
  }
  void update(int i, const Lazy &v) {
    D[i] = R::applyLazy(D[i], v); wm.update(cur[i], v);
  }
  Data query(int l, int r, const T &hi) {
    return wm.query(cur[l], cur[r], hi);
  }
  Data query(int l, int r, const T &lo, const T &hi) {
    return wm.query(cur[l], cur[r], lo, hi);
  }
  template <class F> pair<bool, T *> bsearch(int l, int r, F f) {
    return wm.bsearch(cur[l], cur[r], f);
  }
};

repo_name: wesley-a-leung/Resources

mime_type: text/x-c++


text:
#pragma once
#include <bits/stdc++.h>
using namespace std;

// A collections of functions for 2D prefix sum and difference arrays

// Creates a prefix sum array pre from the 2D array A of size N x M
// pre[i][j] is the sum of all elements in the subarray A[0..i][0..j]
// Indices are 0-indexed
// In practice, has a small constant
// Time Complexity: O(NM)
// Memory Complexity: O(1)
// Tested:
//   Fuzz and Stress Tested
//   https://codeforces.com/contest/635/problem/A
//   https://dmoj.ca/problem/dmpg15s5
template <class C> void partial_sum_2d(const C &A, int N, int M, C &pre) {
  for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) {
    pre[i][j] = A[i][j];
    if (i > 0) pre[i][j] += pre[i - 1][j];
    if (j > 0) pre[i][j] += pre[i][j - 1];
    if (i > 0 && j > 0) pre[i][j] -= pre[i - 1][j - 1];
  }
}

// Creates a difference array diff from the 2D array A of size N x M
// A[i][j] is the sum of all elements in the subarray diff[0..i][0..j]
// Indices are 0-indexed
// In practice, has a small constant
// Time Complexity: O(NM)
// Memory Complexity: O(1)
// Tested:
//   Fuzz and Stress Tested
template <class C>
void adjacent_difference_2d(const C &A, int N, int M, C &diff) {
  for (int i = N - 1; i >= 0; i--) for (int j = M - 1; j >= 0; j--) {
    diff[i][j] = A[i][j];
    if (i > 0) diff[i][j] -= A[i - 1][j];
    if (j > 0) diff[i][j] -= A[i][j - 1];
    if (i > 0 && j > 0) diff[i][j] += A[i - 1][j - 1];
  }
}

// Computes the sum of a subarray A[u..d][l..r] with prefix sum array pre
// Indices are 0-indexed and ranges are inclusive
// In practice, has a moderate constant
// Time Complexity: O(1)
// Memory Complexity: O(1)
// Tested:
//   Fuzz and Stress Tested
//   https://codeforces.com/contest/635/problem/A
template <class C> auto rsq(const C &pre, int u, int d, int l, int r)
    -> typename decay<decltype(pre[d][r])>::type {
  typename decay<decltype(pre[d][r])>::type v = pre[d][r];
  if (u > 0) v -= pre[u - 1][r];
  if (l > 0) v -= pre[d][l - 1];
  if (u > 0 && l > 0) v += pre[u - 1][l - 1];
  return v;
}

// Adds v to the subarray A[u..d][l..r] with difference array diff
//   of size N x M
// Indices are 0-indexed and ranges are inclusive
// In practice, has a moderate constant
// Time Complexity: O(1)
// Memory Complexity: O(1)
// Tested:
//   Fuzz and Stress Tested
//   https://dmoj.ca/problem/dmpg15s5
template <class C, class T>
void add(C &diff, int N, int M, int u, int d, int l, int r, T v) {
  diff[u][l] += v;
  if (d + 1 < N) diff[d + 1][l] -= v;
  if (r + 1 < M) diff[u][r + 1] -= v;
  if (d + 1 < N && r + 1 < M) diff[d + 1][r + 1] += v;
}


text:
#pragma once
#include <bits/stdc++.h>
#include "BitPrefixSumArray.h"
using namespace std;

// Wavelet Matrix supporting 2D aggregation queries where the data can change,
//   but not the keys
// Indices are 0-indexed and ranges are inclusive
// Queries bounded by 3 indices require a commutative operation, while queries
//   bounded by 4 indices also requires the data to be invertible
// Template Arguments:
//   T: the type of the element of the array
//   R: struct supporting point updates and range queries on indices
//     Required Fields:
//       Data: the data type
//       Lazy: the lazy type
//     Required Functions:
//       static qdef(): returns the query default value
//       static merge(l, r): returns the values l of type Data merged with
//         r of type Data, must be associative and commutative
//       constructor(A): takes a vector A of type Data with the initial
//         value of each index
//       update(i, val): updates the index i with the value val
//       query(l, r): queries the range [l, r]
//     Sample Struct: supporting point increments updates and range sum queries
//       struct R {
//         using Data = int;
//         using Lazy = int;
//         static Data qdef() { return 0; }
//         static Data merge(const Data &l, const Data &r) { return l + r; }
//         FenwickTree1D<Data> FT;
//         R(const vector<Data> &A) : FT(A) {}
//         void update(int i, const Lazy &val) { FT.update(i, val); }
//         Data query(int l, int r) { return FT.query(l, r); }
//       };
//   Cmp: the comparator to compare two elements of type T
//     Required Functions:
//       operator (a, b): returns true if and only if a compares less than b
// Constructor Arguments:
//   A: a vector of type T containing the initial keys of the array
//   X: a vector of type R::Data containing the initial data of the array
//   cmp: an instance of the Cmp struct
// Functions:
//   update(i, v): updates the ith data with the lazy value v
//   query(l, r, hi): returns the aggregate value of the data associated with
//     all elements with a key less than or equal to hi (using the comparator)
//     in the range [l, r]
//   query(l, r, lo, hi): returns the aggregate value of the data associated
//     with all elements with a key of not less than lo and not greater than hi
//     (using the comparator) in the range [l, r]
//   bsearch(l, r, f): over all keys in the array, finds the first key k such
//     that query(l, r, k) returns true
// In practice, has a small constant, faster than using a
//   2D Sparse Fenwick Tree or Segment Tree
// Time Complexity:
//   constructor: O((N + C) log N) where C is the time complexity of
//     R's constructor
//   update: O(U log N) where U is the time complexity of R's update function
//   query, bsearch: O(Q log N) where Q is the time complexity of
//     R's query function
// Memory Complexity: O(N + (N log N) / 64 + M log N) where M is the memory
//   complexity of R
// Tested:
//   Fuzz and Stress Tested
//   https://dmoj.ca/problem/dmopc19c7p5
template <class T, class R, class Cmp = less<T>>
struct WaveletMatrixAggregation {
#define clt [&] (const T &a, const T &b) { return cmp(a, b); }
#define cle [&] (const T &a, const T &b) { return !cmp(b, a); }
  using Data = typename R::Data; using Lazy = typename R::Lazy;
  int N, H; Cmp cmp; vector<int> mid; vector<BitPrefixSumArray> B;
  vector<R> D; vector<T> S;
  WaveletMatrixAggregation(vector<T> A, const vector<Data> &X, Cmp cmp = Cmp())
      : N(A.size()), H(N == 0 ? 0 : __lg(N) + 1), cmp(cmp), mid(H),
        B(H, BitPrefixSumArray(N)), S(move(A)) {
    vector<T> temp = S; sort(S.begin(), S.end(), cmp);
    vector<int> C(N), ind(N); for (int i = 0; i < N; i++)
      C[i] = lower_bound(S.begin(), S.end(), temp[i], cmp) - S.begin();
    iota(ind.begin(), ind.end(), 0); D.reserve(H); vector<Data> Y = X;
    for (int h = H - 1; h >= 0; h--) {
      int ph = 1 << h;
      for (int i = 0; i < N; i++) B[h].set(i, C[ind[i]] <= ph - 1);
      mid[h] = stable_partition(ind.begin(), ind.end(), [&] (int i) {
                                  return C[i] <= ph - 1;
                                }) - ind.begin();
      B[h].build(); for (int i = 0; i < N; i++) Y[i] = X[ind[i]];
      D.emplace_back(Y); for (int i = mid[h]; i < N; i++) C[ind[i]] -= ph;
    }
    reverse(D.begin(), D.end());
  }
  void update(int i, const Lazy &v) {
    for (int h = H - 1; h >= 0; h--) {
      if (B[h].get(i)) i = B[h].query(i - 1);
      else i += mid[h] - B[h].query(i - 1);
      D[h].update(i, v);
    }
  }
  template <class F>
  Data qryPre(int h, int cur, int l, int r, const T &v, F f) {
    Data ret = R::qdef(); for (; h >= 0; h--) {
      int ph = 1 << h, ql = B[h].query(l - 1), qr = B[h].query(r);
      if (cur + ph - 1 >= N || f(v, S[cur + ph - 1])) { l = ql; r = qr - 1; }
      else {
        if (ql < qr) ret = R::merge(ret, D[h].query(ql, qr - 1));
        cur += ph; l += mid[h] - ql; r += mid[h] - qr;
      }
    }
    return ret;
  }
  template <class F>
  Data qrySuf(int h, int cur, int l, int r, const T &v, F f) {
    Data ret = R::qdef(); for (; h >= 0; h--) {
      int ph = 1 << h, ql = B[h].query(l - 1), qr = B[h].query(r);
      if (cur + ph - 1 >= N || f(v, S[cur + ph - 1])) {
        if (l - ql <= r - qr)
          ret = R::merge(ret, D[h].query(l + mid[h] - ql, r + mid[h] - qr));
        if (h == 0 && ql < qr) ret = R::merge(ret, D[h].query(ql, qr - 1));
        l = ql; r = qr - 1;
      } else {
        if (h == 0 && l - ql <= r - qr)
          ret = R::merge(ret, D[h].query(l + mid[h] - ql, r + mid[h] - qr));
        cur += ph; l += mid[h] - ql; r += mid[h] - qr;
      }
    }
    return ret;
  }
  Data query(int l, int r, const T &hi) {
    return qryPre(H - 1, 0, l, r, hi, clt);
  }
  Data query(int l, int r, const T &lo, const T &hi) {
    for (int cur = 0, h = H - 1; h >= 0; h--) {
      int ph = 1 << h, ql = B[h].query(l - 1), qr = B[h].query(r);
      bool loLeft = cur + ph - 1 >= N || !cmp(S[cur + ph - 1], lo);
      bool hiLeft = cur + ph - 1 >= N || cmp(hi, S[cur + ph - 1]);
      if (loLeft != hiLeft) {
        Data ret = R::merge(qrySuf(h - 1, cur, ql, qr - 1, lo, cle),
                            qryPre(h - 1, cur + ph, l + mid[h] - ql,
                                   r + mid[h] - qr, hi, clt));
        return h == 0 && ql < qr ? R::merge(ret, D[h].query(ql, qr - 1)) : ret;
      } else if (loLeft) { l = ql; r = qr - 1; }
      else { cur += ph; l += mid[h] - ql; r += mid[h] - qr; }
    }
    return R::qdef();
  }
  template <class F> pair<bool, T *> bsearch(int l, int r, F f) {
    int cur = 0; Data agg = R::qdef(); for (int h = H - 1; h >= 0; h--) {
      int ql = B[h].query(l - 1), qr = B[h].query(r);
      Data val = ql < qr ? D[h].query(ql, qr - 1) : R::qdef();
      if (f(R::merge(agg, val))) { l = ql; r = qr - 1; }
      else {
        cur += 1 << h; agg = R::merge(agg, val);
        l += mid[h] - ql; r += mid[h] - qr;
      }
    }
    return make_pair(cur < N, cur < N ? &S[cur] : nullptr);
  }
#undef clt
#undef cle
};


text:
#pragma once
#include <bits/stdc++.h>
using namespace std;

// Maintains the rank of an element in a multiset
// Indices are 0-indexed and ranges are inclusive
// Template Arguments:
//   T: the type of the values being stored
//   Cmp: the comparator to compare two f(x) values,
//     Required Functions:
//       operator (a, b): returns true if and only if a compares less than b
// Constructor Arguments:
//   v: a vector of type T to initialize the structure
//   SCALE: the value to scale sqrt by
//   cmp: an instance of the Cmp struct
// Functions:
//   rebuild(): rebuilds the multiset by moving all elements in the small
//     container to the large container
//   insert(val): inserts val into the multiset
//   aboveInd(val): returns the index of the smallest element where
//     val compares less than that element
//   ceilingInd(val): returns the index of the smallest element that
//     does not compare less than val
//   floorInd(val): returns the index of the largest element where
//     val does not compare less than that element
//   belowInd(val): returns the index of the largest element that
//     compares less than val
//   aboveVal(val): returns a pointer to the smallest element where
//     val compares less than that element, nullptr if it does not exist
//   ceilingVal(val): returns a pointer to the smallest element that
//     does not compare less than val, nullptr if it does not exist
//   floorVal(val): returns a pointer to the largest element where val does not
//     compare less than that element, nullptr if it does not exist
//   belowVal(val): returns a pointer to the largest element that
//     compares less than val, nullptr if it does not exist
//   above(val): returns a pair containing the index and a pointer to the
//     smallest element where val compares less than that element,
//     pointer is nullptr if it does not exist
//   ceiling(val): returns a pair containing the index and a pointer to the
//     smallest element that does not compare less than val,
//     pointer is nullptr if it does not exist
//   floor(val): returns a pair containing the index and a pointer to the
//     largest element where val does not compare less than that element,
//     pointer is nullptr if it does not exist
//   below(val): returns a pair containing the index and a pointer to the
//     largest element that compares less than val,
//     pointer is nullptr if it does not exist
//   contains(val): returns whether val is in the multiset or not
//   count(lo, hi): returns the number of values in the range [lo, hi]
//   empty(): returns whether the multiset is empty or not
//   size(): returns the number of elements the multiset
//   clear(): clears the multiset
//   values(): returns a vector of the sorted values in the multiset
// In practice, has a very small constant, performs similarly to RootArray,
//   and is faster than balanced binary search trees
// Time Complexity:
//   constructor: O(N)
//   insert: O(1) amortized
//   rebuild: O(sqrt N)
//   empty, size, clear: O(1)
//   floorInd, ceilingInd, aboveInd, belowInd: O(sqrt N) amortized
//   floorVal, ceilingVal, aboveVal, belowVal: O(sqrt N) amortized
//   floor, ceiling, above, below, contains, count: O(sqrt N) amortized
//   values: O(N)
// Memory Complexity: O(N)
// Tested:
//   https://dmoj.ca/problem/dmopc19c3p3
//   https://dmoj.ca/problem/ccc05s5
//   https://mcpt.ca/problem/lcc18c5s3
//   https://codeforces.com/contest/1093/problem/E
template <class T, class Cmp = less<T>> struct SqrtBufferSimple {
  double SCALE; Cmp cmp; vector<T> small, large;
  SqrtBufferSimple(double SCALE = 1, Cmp cmp = Cmp())
      : SCALE(SCALE), cmp(cmp) {}
  SqrtBufferSimple(vector<T> v, double SCALE = 1, Cmp cmp = Cmp())
      : SCALE(SCALE), cmp(cmp), large(move(v)) {
    assert(is_sorted(large.begin(), large.end(), cmp));
  }
  bool rebuild() {
    if (int(small.size()) > SCALE * sqrt(small.size() + large.size())) {
      int lSz = large.size(); sort(small.begin(), small.end(), cmp);
      for (auto &&x : small) large.push_back(x);
      inplace_merge(large.begin(), large.begin() + lSz, large.end(), cmp);
      small.clear(); return true;
    }
    return false;
  }
  void insert(const T &val) { small.push_back(val); }
  int aboveInd(const T &val) {
    rebuild();
    int ret = upper_bound(large.begin(), large.end(), val, cmp)
        - large.begin();
    for (auto &&x : small) ret += !cmp(val, x);
    return ret;
  }
  int ceilingInd(const T &val) {
    rebuild();
    int ret = lower_bound(large.begin(), large.end(), val, cmp)
        - large.begin();
    for (auto &&x : small) ret += cmp(x, val);
    return ret;
  }
  int floorInd(const T &val) { return aboveInd(val) - 1; }
  int belowInd(const T &val) { return ceilingInd(val) - 1; }
  T *aboveVal(const T &val) {
    rebuild(); T *y = nullptr;
    auto it = upper_bound(large.begin(), large.end(), val, cmp);
    if (it != large.end()) y = &*it;
    for (auto &&x : small) if (cmp(val, x) && (!y || cmp(x, *y))) y = &x;
    return y;
  }
  T *ceilingVal(const T &val) {
    rebuild(); T *y = nullptr;
    auto it = lower_bound(large.begin(), large.end(), val, cmp);
    if (it != large.end()) y = &*it;
    for (auto &&x : small) if (!cmp(x, val) && (!y || cmp(x, *y))) y = &x;
    return y;
  }
  T *floorVal(const T &val) {
    rebuild(); T *y = nullptr;
    auto it = upper_bound(large.begin(), large.end(), val, cmp);
    if (it != large.begin()) y = &*--it;
    for (auto &&x : small) if (!cmp(val, x) && (!y || cmp(*y, x))) y = &x;
    return y;
  }
  T *belowVal(const T &val) {
    rebuild(); T *y = nullptr;
    auto it = lower_bound(large.begin(), large.end(), val, cmp);
    if (it != large.begin()) y = &*--it;
    for (auto &&x : small) if (cmp(x, val) && (!y || cmp(*y, x))) y = &x;
    return y;
  }
  pair<int, T *> above(const T &val) {
    rebuild(); T *y = nullptr;
    auto it = upper_bound(large.begin(), large.end(), val, cmp);
    int cnt = it - large.begin(); if (it != large.end()) y = &*it;
    for (auto &&x : small) {
      if (!cmp(val, x)) cnt++;
      else if (!y || cmp(x, *y)) y = &x;
    }
    return make_pair(cnt, y);
  }
  pair<int, T *> ceiling(const T &val) {
    rebuild(); T *y = nullptr;
    auto it = lower_bound(large.begin(), large.end(), val, cmp);
    int cnt = it - large.begin(); if (it != large.end()) y = &*it;
    for (auto &&x : small) {
      if (cmp(x, val)) cnt++;
      else if (!y || cmp(x, *y)) y = &x;
    }
    return make_pair(cnt, y);
  }
  pair<int, T *> floor(const T &val) {
    rebuild(); T *y = nullptr;
    auto it = upper_bound(large.begin(), large.end(), val, cmp);
    int cnt = it - large.begin(); if (it != large.begin()) y = &*--it;
    for (auto &&x : small) if (!cmp(val, x)) {
      cnt++; if (!y || cmp(*y, x)) y = &x;
    }
    return make_pair(--cnt, y);
  }
  pair<int, T *> below(const T &val) {
    rebuild(); T *y = nullptr;
    auto it = lower_bound(large.begin(), large.end(), val, cmp);
    int cnt = it - large.begin(); if (it != large.begin()) y = &*--it;
    for (auto &&x : small) if (cmp(x, val)) {
      cnt++; if (!y || cmp(*y, x)) y = &x;
    }
    return make_pair(--cnt, y);
  }
  bool contains(const T &val) {
    if (binary_search(large.begin(), large.end(), val, cmp)) return true;
    if (rebuild() && binary_search(large.begin(), large.end(), val, cmp))
      return true;
    for (auto &&x : small) if (!cmp(val, x) && !cmp(x, val)) return true;
    return false;
  }
  int count(const T &lo, const T &hi) {
    rebuild();
    int ret = upper_bound(large.begin(), large.end(), hi, cmp)
        - lower_bound(large.begin(), large.end(), lo, cmp);
    for (auto &&x : small) ret += !cmp(x, lo) && !cmp(hi, x);
    return ret;
  }
  bool empty() const { return small.empty() && large.empty(); }
  int size() const { return int(small.size() + large.size()); }
  void clear() { small.clear(); large.clear(); }
  vector<T> values() const {
    vector<T> ret; ret.reserve(size());
    for (auto &&x : small) ret.push_back(x);
    int mid = int(ret.size()); for (auto &&x : large) ret.push_back(x);
    inplace_merge(ret.begin(), ret.begin() + mid, ret.end(), cmp);
    return ret;
  }
};


text:
#pragma once
#include <bits/stdc++.h>
using namespace std;

// Decomposes the array recursively into N ^ (1 / R) containers of
//   size N ^ ((R - 1) / R) multiplied by a scale factor
// Indices are 0-indexed and ranges are inclusive
// Template Arguments:
//   R: the number of recursive levels
//   T: the type of data being stored
// Constructor Arguments:
//   v: a vector of type T to initialize the structure
//   SCALE: the value to scale N ^ ((R - 1) / R) by
// Functions:
//   insert(val, cmp): inserts val before the first index i where
//     cmp(at(i), val) is false assuming the data is sorted by cmp
//   insert_at(k, val): inserts val before index k (0 <= k <= N)
//   erase(val, cmp): erases the element at the first index i where
//     where cmp(at(i), val) and cmp(val, at(i)) are false, if it exists,
//     returns true if the element was erased, false otherwise
//   erase_at(k): erases the element at index k (0 <= k < N)
//   size(): returns the size of the array
//   empty(): returns whether or not the array is empty
//   front(): accessor or modifier for the first element in the array
//   back(): accessor or modifier for the first element in the array
//   push_front(val): adds the val to the front of the array
//   push_back(val): adds the val to the back of the array
//   pop_front(): removes the first element in the array
//   pop_back(): removes the last element in the array
//   at(k): accessor or modifier for the element at index k (0 <= k < N)
//   below(val, cmp): returns the index and a pointer to
//     the last element x where cmp(x, val) is true,
//     or (-1, nullptr) if none exist
//   floor(val, cmp): returns the index and a pointer to
//     the last element x where cmp(val, x) is false,
//     or (-1, nullptr) if none exist
//   ceiling(val, cmp): returns the index and a pointer to
//     the first element x where cmp(x, val) is false,
//     or (N, nullptr) if none exist
//   above(val, cmp): returns the index and a pointer to
//     the first element x where cmp(val, x) is true,
//     or (N, nullptr) if none exist
//   find(val, cmp): returns the index and a pointer to
//     the first element x where cmp(val, x) and cmp(x, val) are false,
//     or (N, nullptr) if none exist
//   values(): returns a vector of all values in the array
//   clear(): clears the array
// In practice, has a very small constant, and is faster than balanced binary
//   search trees when R = 3, and SCALE = 6, even for N >= 1e7
// Time Complexity:
//   constructor: O(N)
//   insert, insert_at, erase, erase_at, push_front, pop_front, at:
//     O(R (I ^ (1 / R))) where I is the total number of insertions
//   below, floor, ceiling, above, find:
//     O(R (I ^ (1 / R))) where I is the total number of insertions
//   front, back, empty, size, pop_back: O(1)
//   push_back: O(1) amortized
//   values, clear: O(N)
// Memory Complexity: O(N)
// Tested:
//   https://dmoj.ca/problem/ds4
//   https://dmoj.ca/problem/cco10p3
//   https://dmoj.ca/problem/ccc05s5
//   https://dmoj.ca/problem/wc18c4s4
//   https://judge.yosupo.jp/problem/predecessor_problem
template <const int R, class T> struct RootArray {
  static_assert(R > 0, "R must be positive");
  int N; vector<RootArray<R - 1, T>> A; double SCALE;
  int getRootN() {
    if (N == 0) return 0;
    int lg = __lg(N); lg -= lg / R; return SCALE * (1 << lg);
  }
  RootArray(double SCALE = 6) : N(0), SCALE(SCALE) { assert(SCALE > 0); }
  RootArray(const vector<T> &v, double SCALE = 6) : N(v.size()), SCALE(SCALE) {
    assert(SCALE > 0); if (N == 0) return;
    int rootN = getRootN(); A.reserve((N - 1) / rootN + 1);
    for (int i = 0; i < N; i += rootN) {
      int en = min(i + rootN, N);
      A.emplace_back(vector<T>(make_move_iterator(v.begin() + i),
                               make_move_iterator(v.begin() + en)), SCALE);
    }
  }
  void split(int i) {
    int rootN = getRootN(); if (int(A[i].size()) > 2 * rootN) {
      vector<T> tmp; tmp.reserve(int(A[i].size()) - rootN);
      while (int(A[i].size()) > rootN) {
        tmp.push_back(move(A[i].back())); A[i].pop_back();
      }
      reverse(tmp.begin(), tmp.end());
      A.emplace(A.begin() + i + 1, move(tmp), SCALE);
    }
  }
  template <class Comp> void insert(const T &val, Comp cmp) {
    if (N++ == 0) { A.emplace_back(SCALE); A.back().insert(val, cmp); return; }
    int i = 0; while (i < int(A.size()) && cmp(A[i].back(), val)) i++;
    if (i >= int(A.size())) i = int(A.size()) - 1;
    A[i].insert(val, cmp); split(i);
  }
  void insert_at(int k, const T &val) {
    if (k == N) { push_back(val); return; }
    N++; int i = 0; while (int(A[i].size()) <= k) k -= int(A[i++].size());
    A[i].insert_at(k, val); split(i);
  }
  template <class Comp> bool erase(const T &val, Comp cmp) {
    int i = 0; while (i < int(A.size()) && cmp(A[i].back(), val)) i++;
    if (i >= int(A.size()) || !A[i].erase(val, cmp)) return false;
    if (A[i].empty()) A.erase(A.begin() + i);
    N--; return true;
  }
  void erase_at(int k) {
    int i = 0; while (int(A[i].size()) <= k) k -= int(A[i++].size());
    N--; A[i].erase_at(k); if (A[i].empty()) A.erase(A.begin() + i);
  }
  int size() const { return N; }
  bool empty() const { return N == 0; }
  const T &front() const { return A.front().front(); }
  T &front() { return A.front().front(); }
  const T &back() const { return A.back().back(); }
  T &back() { return A.back().back(); }
  void push_front(const T &val) {
    if (N++ == 0) { A.emplace_back(SCALE); A.back().push_back(val); return; }
    A.front().push_front(val); split(0);
  }
  void push_back(const T &val) {
    if (N++ == 0) { A.emplace_back(SCALE); A.back().push_back(val); return; }
    A.back().push_back(val); split(int(A.size()) - 1);
  }
  void pop_front() {
    N--; A.front().pop_front();
    if (A.front().empty()) A.erase(A.begin());
  }
  void pop_back() {
    N--; A.back().pop_back();
    if (A.back().empty()) A.pop_back();
  }
  const T &at(int k) const {
    int i = 0; while (int(A[i].size()) <= k) k -= int(A[i++].size());
    return A[i].at(k);
  }
  T &at(int k) {
    int i = 0; while (int(A[i].size()) <= k) k -= int(A[i++].size());
    return A[i].at(k);
  }
  template <class Comp> pair<int, T *> below(const T &val, Comp cmp) {
    int i = 0, k = 0; while (i < int(A.size()) && cmp(A[i].front(), val))
      k += int(A[i++].size());
    if (--i >= 0) k -= int(A[i].size());
    else return make_pair(-1, nullptr);
    pair<int, T *> ret = A[i].below(val, cmp); ret.first += k; return ret;
  }
  template <class Comp> pair<int, T *> floor(const T &val, Comp cmp) {
    int i = 0, k = 0; while (i < int(A.size()) && !cmp(val, A[i].front()))
      k += int(A[i++].size());
    if (--i >= 0) k -= int(A[i].size());
    else return make_pair(-1, nullptr);
    pair<int, T *> ret = A[i].floor(val, cmp); ret.first += k; return ret;
  }
  template <class Comp> pair<int, T *> ceiling(const T &val, Comp cmp) {
    int i = 0, k = 0; while (i < int(A.size()) && cmp(A[i].back(), val))
      k += int(A[i++].size());
    if (i >= int(A.size())) return make_pair(N, nullptr);
    pair<int, T *> ret = A[i].ceiling(val, cmp); ret.first += k; return ret;
  }
  template <class Comp> pair<int, T *> above(const T &val, Comp cmp) {
    int i = 0, k = 0; while (i < int(A.size()) && !cmp(val, A[i].back()))
      k += int(A[i++].size());
    if (i >= int(A.size())) return make_pair(N, nullptr);
    pair<int, T *> ret = A[i].above(val, cmp); ret.first += k; return ret;
  }
  template <class Comp> pair<int, T *> find(const T &val, Comp cmp) {
    pair<int, T *> ret = ceiling(val, cmp);
    if (!ret.second || cmp(val, *(ret.second)) || cmp(*(ret.second), val))
      return make_pair(N, nullptr);
    return ret;
  }
  vector<T> values() const {
    vector<T> ret; ret.reserve(N);
    for (auto &&ai : A) for (auto &&aij : ai.values()) ret.push_back(aij);
    return ret;
  }
  void clear() { N = 0; A.clear(); }
};

template <class T> struct RootArray<1, T> : public vector<T> {
  using vector<T>::begin; using vector<T>::end; using vector<T>::size;
  using vector<T>::at; RootArray(double = 6) {}
  RootArray(const vector<T> &v, double = 6) : vector<T>(v) {}
  template <class Comp> void insert(const T &val, Comp cmp) {
    vector<T>::insert(lower_bound(begin(), end(), val, cmp), val);
  }
  void insert_at(int k, const T &val) { vector<T>::insert(begin() + k, val); }
  template <class Comp> bool erase(const T &val, Comp cmp) {
    auto it = lower_bound(begin(), end(), val, cmp);
    if (it == end() || cmp(*it, val) || cmp(val, *it)) return false;
    vector<T>::erase(it); return true;
  }
  void erase_at(int k) { vector<T>::erase(begin() + k); }
  void push_front(const T &val) { vector<T>::insert(begin(), val); }
  void pop_front() { vector<T>::erase(begin()); }
  template <class Comp> pair<int, T *> below(const T &val, Comp cmp) {
    int i = lower_bound(begin(), end(), val, cmp) - begin() - 1;
    return make_pair(i, i < 0 ? nullptr : &at(i));
  }
  template <class Comp> pair<int, T *> floor(const T &val, Comp cmp) {
    int i = upper_bound(begin(), end(), val, cmp) - begin() - 1;
    return make_pair(i, i < 0 ? nullptr : &at(i));
  }
  template <class Comp> pair<int, T *> ceiling(const T &val, Comp cmp) {
    int i = lower_bound(begin(), end(), val, cmp) - begin();
    return make_pair(i, i >= int(size()) ? nullptr : &at(i));
  }
  template <class Comp> pair<int, T *> above(const T &val, Comp cmp) {
    int i = upper_bound(begin(), end(), val, cmp) - begin();
    return make_pair(i, i >= int(size()) ? nullptr : &at(i));
  }
  template <class Comp> pair<int, T *> find(const T &val, Comp cmp) {
    pair<int, T *> ret = ceiling(val, cmp);
    if (!ret.second || cmp(val, *(ret.second)) || cmp(*(ret.second), val))
      return make_pair(size(), nullptr);
    return ret;
  }
  RootArray<1, T> values() const { return *this; }
};


text:
#pragma once
#include <bits/stdc++.h>
using namespace std;

// Maintains the rank of an element in a multiset, allowing for multiple
//   insertions of the same element at the same time (including negative)
// Note that elements with a count of 0 or negative are still in the multiset
//   as elements cannot be removed
// Indices are 0-indexed and ranges are inclusive
// Template Arguments:
//   T: the type of the values being stored
//   CountType: the type of the count of elements in the set
//   Cmp: the comparator to compare two f(x) values,
//     Required Functions:
//       operator (a, b): returns true if and only if a compares less than b
// Constructor Arguments:
//   v: a vector of type pair<T, CountType> to initialize the structure
//   SCALE: the value to scale sqrt by
//   cmp: an instance of the Cmp struct
// Functions:
//   rebuild(): rebuilds the multiset by moving all elements in the small
//     container to the large container
//   insert(p): inserts the element p.first with a count of p.second
//     into the multiset
//   emplace(v, c): inserts the element v with a count of c
//     into the multiset
//   aboveInd(val): returns the index of the smallest element where
//     val compares less than that element
//   ceilingInd(val): returns the index of the smallest element that
//     does not compare less than val
//   floorInd(val): returns the index of the largest element where
//     val does not compare less than that element
//   belowInd(val): returns the index of the largest element that
//     compares less than val
//   contains(val): returns whether val is in the multiset or not
//   count(lo, hi): returns the number of values in the range [lo, hi]
//   empty(): returns whether the multiset is empty or not
//   count(): returns the number of elements the multiset
//   clear(): clears the multiset
//   values(): returns a vector of pairs containing the sorted values and
//     their count in the multiset
// In practice, has a very small constant, performs similarly to RootArray,
//   and is faster than balanced binary search trees
// Time Complexity:
//   constructor: O(N)
//   insert: O(1) amortized
//   rebuild: O(sqrt N)
//   count(): O(1)
//   floor, ceiling, above, below, contains, count(val), count(lo, hi):
//     O(sqrt N) amortized
//   valuesAndCount: O(N)
// Memory Complexity: O(N)
// Tested:
//   https://dmoj.ca/problem/apio19p3
//   https://dmoj.ca/problem/ioi01p1
template <class T, class CountType, class Cmp = less<T>>
struct SqrtBuffer {
  struct PairCmp {
    Cmp cmp; PairCmp(Cmp cmp) : cmp(cmp) {}
    bool operator () (const pair<T, CountType> &a,
                      const pair<T, CountType> &b) const {
      return cmp(a.first, b.first);
    }
  };
  CountType tot; double SCALE; PairCmp pcmp;
  vector<pair<T, CountType>> small, large;
  SqrtBuffer(double SCALE = 1, Cmp cmp = Cmp())
    : tot(CountType()), SCALE(SCALE), pcmp(PairCmp(cmp)) {}
  SqrtBuffer(vector<pair<T, CountType>> v, double SCALE = 1, Cmp cmp = Cmp())
      : tot(CountType()), SCALE(SCALE), pcmp(PairCmp(cmp)), large(move(v)) {
    assert(is_sorted(large.begin(), large.end(), pcmp));
    resizeUnique(large); for (auto &&p : large) tot += p.second;
  }
  void resizeUnique(vector<pair<T, CountType>> &v) {
    if (!v.empty()) {
      int j = 0; for (int i = 1; i < int(v.size()); i++) {
        if (Cmp()(v[i].first, v[j].first) || Cmp()(v[j].first, v[i].first)) {
          v[++j] = v[i]; v[j].second += v[j - 1].second;
        } else v[j].second += v[i].second;
      }
      v.erase(v.begin() + j + 1, v.end());
    }
  }
  bool rebuild() {
    if (int(small.size()) > SCALE * sqrt(small.size() + large.size())) {
      int lSz = large.size(); sort(small.begin(), small.end(), pcmp);
      for (int i = lSz - 1; i > 0; i--) large[i].second -= large[i - 1].second;
      for (auto &&p : small) large.push_back(p);
      inplace_merge(large.begin(), large.begin() + lSz, large.end(), pcmp);
      resizeUnique(large); small.clear(); return true;
    }
    return false;
  }
  void insert(const pair<T, CountType> &p) {
    small.push_back(p); tot += p.second;
  }
  void emplace(const T &v, const CountType &c) {
    small.emplace_back(v, c); tot += c;
  }
  CountType aboveInd(const T &val) {
    rebuild();
    int ind = upper_bound(large.begin(), large.end(),
                          make_pair(val, CountType()), pcmp)
        - large.begin();
    CountType ret = ind == 0 ? CountType() : large[ind - 1].second;
    for (auto &&p : small) if (!Cmp()(val, p.first)) ret += p.second;
    return ret;
  }
  CountType ceilingInd(const T &val) {
    rebuild();
    int ind = lower_bound(large.begin(), large.end(),
                          make_pair(val, CountType()), pcmp)
        - large.begin();
    CountType ret = ind == 0 ? CountType() : large[ind - 1].second;
    for (auto &&p : small) if (Cmp()(p.first, val)) ret += p.second;
    return ret;
  }
  CountType floorInd(const T &val) { return aboveInd(val) - 1; }
  CountType belowInd(const T &val) { return ceilingInd(val) - 1; }
  bool contains(const T &val) {
    if (binary_search(large.begin(), large.end(),
        make_pair(val, CountType()), pcmp)) return true;
    if (rebuild() && binary_search(large.begin(), large.end(),
                                   make_pair(val, CountType()), pcmp))
      return true;
    for (auto &&p : small) if (!Cmp()(val, p.first) && !Cmp()(p.first, val))
      return true;
    return false;
  }
  CountType count(const T &lo, const T &hi) {
    rebuild();
    int ind = upper_bound(large.begin(), large.end(),
                          make_pair(hi, CountType()), pcmp)
        - large.begin();
    CountType ret = ind == 0 ? CountType() : large[ind - 1].second;
    ind = lower_bound(large.begin(), large.end(),
                      make_pair(lo, CountType()), pcmp)
        - large.begin();
    ret -= ind == 0 ? CountType() : large[ind - 1].second;
    for (auto &&p : small) if (!Cmp()(p.first, lo) && !Cmp()(hi, p.first))
      ret += p.second;
    return ret;
  }
  CountType count() const { return tot; }
  void clear() { tot = CountType(); small.clear(); large.clear(); }
  vector<pair<T, CountType>> valuesAndCount() const {
    vector<pair<T, CountType>> ret; ret.reserve(large.size() + small.size());
    for (auto &&p : small) ret.push_back(p);
    int mid = int(ret.size()); for (auto &&p : large) ret.push_back(p);
    inplace_merge(ret.begin(), ret.begin() + mid, ret.end(), pcmp);
    resizeUnique(ret); return ret;
  }
};


text:
#pragma once
#include <bits/stdc++.h>
#include "../trees/PersistentArray.h"
using namespace std;

// Persistent Union Find by size where copy assignment/constructor creates
//   a new version of the data structure
// Indices are 0-indexed
// Constructor Arguments:
//   N: the number of elements in the set
// Fields:
//   UF: a vector of integers representing the parent of each element in the
//     tree, or the negative of the size of the set if that element is a root
//   cnt: the current number of disjoint sets
// Functions:
//   find(v): finds the root of the set containing element v in the
//     current version
//   join(v, w): merges the sets containing v and w, returns true if they
//     were originally disjoint before the merge in the current version,
//     false otherwise
//   connected(v, w): returns true if v and w are in the same set in the
//     current version, false otherwise
//   getSize(v): returns the size of the set containing element v in the
//     current version
// In practice, has a moderate constant
// Time Complexity:
//   constructor: O(N)
//   find, join, connected, getSize: O((log N)^2)
// Memory Complexity: O(N log N)
// Tested:
//   https://judge.yosupo.jp/problem/persistent_unionfind
struct PersistentUnionFind {
  PersistentArray<int> UF; int cnt;
  PersistentUnionFind(int N) : UF(N, -1), cnt(N) {}
  int find(int v) { int ufv = UF.get(v); return ufv < 0 ? v : find(ufv); }
  bool join(int v, int w) {
    if ((v = find(v)) == (w = find(w))) return false;
    int ufv = UF.get(v), ufw = UF.get(w);
    if (ufv > ufw) { swap(v, w); swap(ufv, ufw); }
    UF.set(v, ufv + ufw); UF.set(w, v); cnt--; return true;
  }
  bool connected(int v, int w) { return find(v) == find(w); }
  int getSize(int v) { return -UF.get(find(v)); }
};


text:
#pragma once
#include <bits/stdc++.h>
using namespace std;

// Union Find by size supporting undos
// Indices are 0-indexed
// Constructor Arguments:
//   N: the number of elements in the set
// Fields:
//   UF: a vector of integers representing the parent of each element in the
//     tree, or the negative of the size of the set if that element is a root
//   cnt: the current number of disjoint sets
//   history: a vector of tuples storing the history of all join calls
// Functions:
//   find(v): finds the root of the set containing element v
//   join(v, w): merges the sets containing v and w, returns true if they
//     were originally disjoint before the merge, false otherwise
//   undo(): undoes the last call to join regardless of its return value
//     by popping from the history stack
//   connected(v, w): returns true if v and w are in the same set,
//     false otherwise
//   getSize(v): returns the size of the set containing element v
// In practice, has a small constant
// Time Complexity:
//   constructor: O(N)
//   find, join, connected, getSize: O(log N)
//   undo: O(1)
// Memory Complexity: O(N + Q) for Q calls to join
// Tested:
//   https://dmoj.ca/problem/apio19p2
struct UnionFindUndo {
  vector<int> UF; int cnt; vector<tuple<int, int, int>> history;
  UnionFindUndo(int N) : UF(N, -1), cnt(N) { history.reserve(N); }
  int find(int v) { return UF[v] < 0 ? v : find(UF[v]); }
  bool join(int v, int w) {
    if ((v = find(v)) == (w = find(w))) {
      history.emplace_back(v, w, 0); return false;
    }
    if (UF[v] > UF[w]) swap(v, w);
    history.emplace_back(v, w, UF[w]);
    UF[v] += UF[w]; UF[w] = v; cnt--; return true;
  }
  void undo() {
    int v, w, ufw; tie(v, w, ufw) = history.back(); history.pop_back();
    if (ufw == 0) return;
    UF[w] = ufw; UF[v] -= UF[w]; cnt++;
  }
  bool connected(int v, int w) { return find(v) == find(w); }
  int getSize(int v) { return -UF[find(v)]; }
};


text:
#pragma once
#include <bits/stdc++.h>
using namespace std;

// Weighted Union Find by size with path compression
// Indices are 0-indexed
// Template Arguments:
//   T: the type of the weight
//   Op: a struct with the cumulative operation to combine weights
//     Required Functions:
//       operator (l, r): combines the values l and r, must be associative and
//         commutative
// Constructor Arguments:
//   W: a vector of type T of the weights of each element in the set
//   op: an instance of the Op struct
// Fields:
//   UF: a vector of integers representing the parent of each element in the
//     tree, or the negative of the size of the set if that element is a root
//   W: a vector of type T representing the weight of all elements in the
//     connected component if and only if that element is a root
//   cnt: the current number of disjoint sets
// Functions:
//   find(v): finds the root of the set containing element v
//   join(v, w): merges the sets containing v and w, returns true if they
//     were originally disjoint before the merge, false otherwise
//   connected(v, w): returns true if v and w are in the same set,
//     false otherwise
//   getSize(v): returns the size of the set containing element v
//   getWeight(v): returns the weight of the set containing element v
// In practice, has a small constant
// Time Complexity:
//   constructor: O(N)
//   find, join, connected: O(alpha N) amortized, O(log N) worse case
//   getSize, getWeight: O(alpha N) amortized, O(log N) worse case
// Memory Complexity: O(N)
// Tested:
//   https://dmoj.ca/problem/noi15p5
template <class T, class Op> struct WeightedUnionFind {
  vector<int> UF; vector<T> W; int cnt; Op op;
  WeightedUnionFind(vector<T> W, Op op = Op())
      : UF(W.size(), -1), W(move(W)), cnt(UF.size()), op(op) {}
  int find(int v) { return UF[v] < 0 ? v : UF[v] = find(UF[v]); }
  bool join(int v, int w) {
    if ((v = find(v)) == (w = find(w))) return false;
    if (UF[v] > UF[w]) swap(v, w);
    UF[v] += UF[w]; UF[w] = v; W[v] = op(move(W[v]), move(W[w])); cnt--;
    return true;
  }
  bool connected(int v, int w) { return find(v) == find(w); }
  int getSize(int v) { return -UF[find(v)]; }
  T &getWeight(int v) { return W[find(v)]; }
};


text:
#pragma once
#include <bits/stdc++.h>
using namespace std;

// Union Find by size with path compression
// Indices are 0-indexed
// Constructor Arguments:
//   N: the number of elements in the set
// Fields:
//   UF: a vector of integers representing the parent of each element in the
//     tree, or the negative of the size of the set if that element is a root
//   cnt: the current number of disjoint sets
// Functions:
//   find(v): finds the root of the set containing element v
//   join(v, w): merges the sets containing v and w, returns true if they
//     were originally disjoint before the merge, false otherwise
//   connected(v, w): returns true if v and w are in the same set,
//     false otherwise
//   getSize(v): returns the size of the set containing element v
// In practice, has a small constant
// Time Complexity:
//   constructor: O(N)
//   find, join, connected, getSize: O(alpha N) amortized, O(log N) worse case
// Memory Complexity: O(N)
// Tested:
//   Fuzz and Stress Tested
//   https://judge.yosupo.jp/problem/unionfind
//   https://dmoj.ca/problem/ds2
//   https://atcoder.jp/contests/abc177/tasks/abc177_d
struct UnionFind {
  vector<int> UF; int cnt; UnionFind(int N) : UF(N, -1), cnt(N) {}
  int find(int v) { return UF[v] < 0 ? v : UF[v] = find(UF[v]); }
  bool join(int v, int w) {
    if ((v = find(v)) == (w = find(w))) return false;
    if (UF[v] > UF[w]) swap(v, w);
    UF[v] += UF[w]; UF[w] = v; cnt--; return true;
  }
  bool connected(int v, int w) { return find(v) == find(w); }
  int getSize(int v) { return -UF[find(v)]; }
};


text:
#pragma once
#include <bits/stdc++.h>
using namespace std;

// Weighted Union Find by size supporting undos
// Indices are 0-indexed
// Template Arguments:
//   T: the type of the weight
//   Op: a struct with the cumulative operation to combine weights
//     Required Functions:
//       operator (l, r): combines the values l and r, must be associative and
//         commutative
// Constructor Arguments:
//   W: a vector of type T of the weights of each element in the set
//   op: an instance of the Op struct
// Fields:
//   UF: a vector of integers representing the parent of each element in the
//     tree, or the negative of the size of the set if that element is a root
//   W: a vector of type T representing the weight of all elements in the
//     connected component if and only if that element is a root
//   cnt: the current number of disjoint sets
//   history: a vector of tuples storing the history of all join calls
// Functions:
//   find(v): finds the root of the set containing element v
//   join(v, w): merges the sets containing v and w, returns true if they
//     were originally disjoint before the merge, false otherwise
//   undo(): undoes the last call to join regardless of its return value
//     by popping from the history stack
//   connected(v, w): returns true if v and w are in the same set,
//     false otherwise
//   getSize(v): returns the size of the set containing element v
//   getWeight(v): returns the weight of the set containing element v
// In practice, has a small constant
// Time Complexity:
//   constructor: O(N)
//   find, join, connected, getSize, getWeight: O(log N)
//   undo: O(1)
// Memory Complexity: O(N + Q) for Q calls to join
// Tested:
//   https://judge.yosupo.jp/problem/dynamic_graph_vertex_add_component_sum
template <class T, class Op> struct WeightedUnionFindUndo {
  vector<int> UF; vector<T> W; int cnt;
  vector<tuple<int, int, int, T, T>> history; Op op;
  WeightedUnionFindUndo(vector<T> W, Op op = Op())
      : UF(W.size(), -1), W(move(W)), cnt(UF.size()), op(op) {
    history.reserve(W.size());
  }
  int find(int v) { return UF[v] < 0 ? v : find(UF[v]); }
  bool join(int v, int w) {
    if ((v = find(v)) == (w = find(w))) {
      history.emplace_back(v, w, 0, W[v], W[w]); return false;
    }
    if (UF[v] > UF[w]) swap(v, w);
    history.emplace_back(v, w, UF[w], W[v], W[w]);
    UF[v] += UF[w]; UF[w] = v; W[v] = op(move(W[v]), move(W[w])); cnt--;
    return true;
  }
  void undo() {
    int v, w, ufw; T wv, ww; tie(v, w, ufw, wv, ww) = history.back();
    history.pop_back(); if (ufw == 0) return;
    UF[w] = ufw; UF[v] -= UF[w]; W[v] = wv; W[w] = ww; cnt++;
  }
  bool connected(int v, int w) { return find(v) == find(w); }
  int getSize(int v) { return -UF[find(v)]; }
  T &getWeight(int v) { return W[find(v)]; }
};


text:
#pragma once
#include <bits/stdc++.h>
#include "../../search/BinarySearch.h"
using namespace std;

// Union Find by size supporting queries for a past version of
//   the data structure but only allowed for updates to the latest version
// Constructor Arguments:
//   N: the number of elements in the set
// Fields:
//   UF: a vector of vectors of pairs containing the time that the parent or
//     size has changed for an element, and the parent or size of the element
//     at that time; the second element in the pair represents the parent of
//     that element in the tree, or the negative of the size of the set if that
//     element is a root
//   cnt: a vector of pairs containing the time that the number of disjoint
//     sets changes and the number of disjoint sets at that time
//   curTime: the current time, begins at -1 before any joins, and increases
//     by 1 after every join call
// Functions:
//   find(t, v): finds the root of the set containing element v at time t
//   join(v, w): merges the sets containing v and w, returns true if they
//     were originally disjoint before the merge, false otherwise
//   connected(t, v, w): returns true if v and w are in the same set,
//     at time t, false otherwise
//   getSize(t, v): returns the size of the set containing element v at time t
//   getCnt(t): returns the number of disjoint sets at time t
//   getFirst(v, w): returns the first time that elements v and w are in the
//     same set, -1 if v == w and curTime + 1 if they are never in the
//     same set
// In practice, find, join, connected, getSize, getCnt have a small constant,
//   getFirst has a very small constant
// Time Complexity:
//   constructor: O(N)
//   find, join, connected, getSize, getCnt: O(log N)
//   getFirst: O(log N log Q) after Q join operations
// Memory Complexity: O(N)
// Tested:
//   https://codeforces.com/contest/1253/problem/F
struct PartiallyPersistentUnionFind {
  vector<vector<pair<int, int>>> UF; vector<pair<int, int>> cnt; int curTime;
  PartiallyPersistentUnionFind(int N)
      : UF(N, vector<pair<int, int>>{make_pair(curTime, -1)}),
        cnt{make_pair(curTime, N)}, curTime(-1) {}
  int find(int t, int v) {
    return UF[v].back().second < 0 || UF[v].back().first > t
           ? v : find(t, UF[v].back().second);
  }
  bool join(int v, int w) {
    curTime++;
    if ((v = find(curTime, v)) == (w = find(curTime, w))) return false;
    int ufv = UF[v].back().second, ufw = UF[w].back().second;
    if (ufv > ufw) { swap(v, w); swap(ufv, ufw); }
    UF[v].emplace_back(curTime, ufv + ufw); UF[w].emplace_back(curTime, v);
    cnt.emplace_back(curTime, cnt.back().second - 1); return true;
  }
  bool connected(int t, int v, int w) { return find(t, v) == find(t, w); }
  int getSize(int t, int v) {
    v = find(t, v);
    return -prev(upper_bound(UF[v].begin(), UF[v].end(),
                             make_pair(t, INT_MAX)))->second;
  }
  int getCnt(int t) {
    return prev(upper_bound(cnt.begin(), cnt.end(),
                            make_pair(t, INT_MAX)))->second;
  }
  int getFirst(int v, int w) {
    return bsearch<FIRST>(-1, curTime + 1, [&] (int x) {
      return connected(x, v, w);
    });
  }
};


text:
#pragma once
#include <bits/stdc++.h>
using namespace std;

// Persistent Array where copy assignment/constructor creates
//   a new version of the data structure
// Indices are 0-indexed
// Template Arguments:
//   T: the type of each element
// Constructor Arguments:
//   N: the size of the array
//   A: a vector of type T
// Functions:
//   get(k): returns a constant reference to the kth element in the
//     current version
//   set(k, v): sets the kth element to index v in the current version
//   size(): returns the size of the array
// In practice, has a moderate constant
// Time Complexity:
//   constructor, get, set: O(log N)
//   size: O(1)
// Memory Complexity: O(N + Q log N) for Q operations
// Tested:
//   https://judge.yosupo.jp/problem/persistent_queue
template <class T> struct PersistentArray {
  struct Node; using ptr = shared_ptr<Node>; int N; ptr root;
  struct Node {
    T v; ptr l, r;
    Node(const T &v, const ptr &l = ptr(), const ptr &r = ptr())
        : v(v), l(l), r(r) {}
  };
  ptr build(const vector<T> &A, int l, int r) {
    if (l >= r) return l == r ? make_shared<Node>(A[l]) : ptr();
    int m = l + (r - l) / 2;
    ptr left = build(A, l, m - 1); ptr right = build(A, m + 1, r);
    return make_shared<Node>(A[m], left, right);
  }
  ptr dfs(const ptr &x, int l, int r, int k, const T &v) {
    int m = l + (r - l) / 2;
    if (k < m) return make_shared<Node>(x->v, dfs(x->l, l, m - 1, k, v), x->r);
    else if (k > m)
      return make_shared<Node>(x->v, x->l, dfs(x->r, m + 1, r, k, v));
    else return make_shared<Node>(v, x->l, x->r);
  }
  PersistentArray(const vector<T> &A)
      : N(A.size()), root(build(A, 0, N - 1)) {}
  PersistentArray(int N, const T &v = T())
      : PersistentArray(vector<T>(N, v)) {}
  const T &get(int k) const {
    ptr x = root; for (int l = 0, r = N - 1, m; k != (m = l + (r - l) / 2);) {
      if (k < m) { x = x->l; r = m - 1; }
      else { x = x->r; l = m + 1; }
    }
    return x->v;
  }
  void set(int k, const T &v) { root = dfs(root, 0, N - 1, k, v); }
  int size() const { return N; }
};


text:
#pragma once
#include <bits/stdc++.h>
using namespace std;

// Builds a cartesian tree where all vertices j in vertex i's subtree have
//   !cmp(A[i], A[j]) and (cmp(A[j], A[i]) or j < i)
// Indices are 0-indexed
// Template Arguments:
//   T: the type of each element in the array
//   Cmp: the comparator to compare two values,
//       convention is same as std::priority_queue in STL
//     Required Functions:
//       operator (a, b): returns true if and only if a compares less than b
// Function Arguments:
//   A: a vector of type T
//   cmp: an instance of the Cmp struct
// Return Value: a vector of integers representing the parent of each vertex
//   in the cartesian tree, or -1 if that vertex is the root
// In practice, has a moderate constant
// Time Complexity: O(N)
// Memory Complexity: O(N)
// Tested:
//   https://judge.yosupo.jp/problem/cartesian_tree
template <class T, class Cmp = less<T>>
vector<int> cartesianTree(const vector<T> &A, Cmp cmp = Cmp()) {
  int N = A.size(), top = 0; vector<int> stk(N), P(N, -1);
  for (int i = 0; i < N; stk[top++] = i++) {
    int last = -1; while (top > 0 && cmp(A[stk[top - 1]], A[i])) {
      if (last != -1) P[last] = stk[top - 1];
      last = stk[--top];
    }
    if (last != -1) P[last] = i;
    if (top > 0) P[i] = stk[top - 1];
  }
  return P;
}


text:
#pragma once
#include <bits/stdc++.h>
using namespace std;

// Binary Trie
// Template Arguments:
//   T: the type of the values being inserted and queried
// Constructor Arguments:
//   MX: the maximum value of v for any function call
// Functions:
//   empty(): returns whether the trie is empty or not
//   insert(v): inserts the value v into the trie if it doesn't already exist,
//     returns whether it was inserted or not
//   contains(v): returns whether the trie contains the value v
//   erase(v): erases the value v into the trie if it exists,
//     returns whether it was erased or not
//   minXor(v): returns the minimum value of v xor any value in the trie, trie
//     cannot be empty
//   maxXor(v): returns the maximum value of v xor any value in the trie, trie
//     cannot be empty
// Time Complexity:
//   constructor: O(1)
//   insert, contains, erase, minXor, maxXor: O(log MX)
// Memory Complexity: O(Q log MX) for Q insertions
// Tested:
//   Fuzz Tested
//   https://judge.yosupo.jp/problem/set_xor_min
//   https://www.acmicpc.net/problem/16903
template <class T> struct BinaryTrie {
  struct Node : public array<int, 2> {
    Node() : array<int, 2>() { fill(-1); }
  };
  vector<Node> TR; vector<int> deleted; int root, lg;
  int makeNode() {
    if (deleted.empty()) { TR.emplace_back(); return int(TR.size()) - 1; }
    int i = deleted.back(); deleted.pop_back(); TR[i] = Node(); return i;
  }
  BinaryTrie(T MX)
      : root(-1), lg(MX == 0 ? 0 : __lg(MX)) {}
  bool empty() { return root == -1; }
  bool insert(T v) {
    bool ret = false; if (root == -1) root = makeNode();
    for (int cur = root, i = lg; i >= 0; i--) {
      bool b = (v >> i) & 1;
      if (TR[cur][b] == -1) { int n = makeNode(); ret = true; TR[cur][b] = n; }
      cur = TR[cur][b];
    }
    return ret;
  }
  bool contains(T v) {
    if (root == -1) return false;
    for (int cur = root, i = lg; i >= 0; i--) {
      bool b = (v >> i) & 1; if (TR[cur][b] == -1) return false;
      cur = TR[cur][b];
    }
    return true;
  }
  bool erase(T v) {
    bool ret = false;
    function<int(int, int)> rec = [&] (int cur, int i) {
      if (i == -1) { ret = true; deleted.push_back(cur); return -1; }
      bool b = (v >> i) & 1; if (TR[cur][b] == -1) return cur;
      TR[cur][b] = rec(TR[cur][b], i - 1);
      if (TR[cur][0] == -1 && TR[cur][1] == -1) {
        assert(ret); deleted.push_back(cur); return -1;
      } else return cur;
    };
    if (root != -1) root = rec(root, lg);
    return ret;
  }
  T minXor(T v) {
    T ret = 0; for (int cur = root, i = lg; i >= 0; i--) {
      bool b = (v >> i) & 1; if (TR[cur][b] == -1) {
        ret ^= T(1) << i; cur = TR[cur][b ^ 1];
      } else cur = TR[cur][b];
    }
    return ret;
  }
  T maxXor(T v) {
    T ret = 0; for (int cur = root, i = lg; i >= 0; i--) {
      bool b = (v >> i) & 1; if (TR[cur][b ^ 1] == -1) cur = TR[cur][b];
      else { ret ^= T(1) << i; cur = TR[cur][b ^ 1]; }
    }
    return ret;
  }
};


text:
#pragma once
#include <bits/stdc++.h>
#include "Splay.h"
using namespace std;

// Operations on ranges of a dynamic array, backed by a splay tree
// Supports point/range updates/queries, range reversals,
//   and binary searching as long as Node contains the appropriate flags
// Also supports insertion and erasing at an index or with a comparator
//   (as long as all values in the tree are sorted by the same comparator),
//   with insert_at inserting an element or range before the specified index
// Indices are 0-indexed and ranges are inclusive
// Template Arguments:
//   Node: typedef/using of the node class containing information about
//       each node in the tree
//     Required Fields:
//       Data: the data type
//       Lazy: the lazy type
//       static const RANGE_UPDATES: a boolean indicating whether
//         range updates are permitted
//       static const RANGE_QUERIES: a boolean indicating whether
//         range queries are permitted
//       static const RANGE_REVERSALS: a boolean indicating whether
//         range reversals are permitted
//       l: a pointer to the left child
//       r: a pointer to the right child
//       val: the value of type Data being stored
//       lz: only required if RANGE_UPDATES is true, the value of type
//         Lazy to be propagated
//       sbtr: only required if RANGE_QUERIES is true, the aggregate
//         value of type Data for the subtree
//     Required Functions:
//       constructor(v): initializes a node with the value v
//       propagate(): propagates the current node's lazy information
//         (including rev) to its children
//       apply(v): applies the lazy value v to the node
//       reverse(): only required if RANGE_REVERSALS is true, reverse
//         this node's subtree (aggregate data and any lazy
//         flags should be reversed)
//       static qdef(): only required if RANGE_QUERIES is true, returns the
//         query default value
// Constructor Arguments:
//   N: the size of the array
//   A: the array
// Functions:
//   insert_at(i, v): inserts a node before index i by passing v to the
//     node constructor
//   insert_at(i, A): inserts the elements in the vector A before index i,
//     where the elements are passed to the node constructor in the order
//     they appear
//   insert(v, cmp): inserts a node before the first of node y where
//     cmp(y->val, v) returns false, by passing v to the node constructor
//   erase_at(i): erases the node at index i
//   erase_at(j): erases the nodes between index i and j inclusive
//   erase(v, cmp): erases the first node y where both cmp(y->val, v) and
//     cmp(v, y->val) returns false
//   update(i, v): updates the node at index i with the lazy value v
//   update(i, j, v): only valid if Node::RANGE_UPDATES is true, updates the
//     nodes between index i and j inclusive with the lazy value v
//   reverse(i, j): only valid if Node::RANGE_REVERSALS is true, reverses the
//     nodes between index i and j inclusive
//   size(): returns the number of nodes in the trees
//   at(i): returns the value of the node at index i
//   lower_bound(v, cmp): returns the index and pointer to the value of the
//     first node y such that cmp(y->val, v) returns false, returns
//     {size(), nullptr} if none exist
//   upper_bound(v, cmp): returns the index and pointer to the value of the
//     first node y such that cmp(v, y->val) returns true, returns
//     {size(), nullptr} if none exist
//   find(v, cmp): returns the index and pointer to the value of the
//     first node y such that both cmp(y->val, v) and cmp(v, y->val) return
//     false, returns {size(), nullptr} if none exist
//   query(i, j): only valid if Node::RANGE_QUERIES is true, returns the
//     aggregate value of the nodes between index i and j inclusive,
//     Node::qdef() if empty
//   values(): returns a vector of the values of all nodes in the tree
// Time Complexity:
//   constructor: O(N)
//   insert, insert_at: O(log N + M) amortized for M inserted elements
//   erase: erase_at: O(log N + M) amortized for M deleted elements
//   update, reverse, at, lower_bound, upper_bound, find, query:
//     O(log N) amortized
//   values: O(N)
//   size: O(1)
// Memory Complexity: O(N)
// Tested:
//   https://dmoj.ca/problem/ds4 (insert, erase, at, find, values)
//   https://codeforces.com/contest/863/problem/D (reverse)
//   https://dmoj.ca/problem/acc1p1 (reverse, range queries)
//   https://dmoj.ca/problem/noi05p2
//     (insert_at, erase_at, range update, reverse, range queries)
//   https://judge.yosupo.jp/problem/dynamic_sequence_range_affine_range_sum
//     (insert_at, erase_at, range update, reverse, range queries)
template <class Node> struct DynamicRangeOperations : public Splay<Node> {
  using Data = typename Node::Data; using Lazy = typename Node::Lazy;
  Node *root; using Tree = Splay<Node>;
  using Tree::makeNode; using Tree::applyToRange; using Tree::select;
  using Tree::getFirst; using Tree::build; using Tree::clear;
  template <class T>
  DynamicRangeOperations(const vector<T> &A) : root(build(A)) {}
  DynamicRangeOperations() : root(nullptr) {}
  template <class T> void insert_at(int i, const T &v) {
    applyToRange(root, i, i - 1, [&] (Node *&x) { x = makeNode(v); });
  }
  template <class T> void insert_at(int i, const vector<T> &A) {
    applyToRange(root, i, i - 1, [&] (Node *&x) { x = build(A); });
  }
  template <class T, class Comp> void insert(const T &v, Comp cmp) {
    insert_at(getFirst(root, v, cmp).first, v);
  }
  void erase_at(int i) {
    applyToRange(root, i, i, [&] (Node *&x) { clear(x); x = nullptr; });
  }
  void erase_at(int i, int j) {
    if (i <= j)
      applyToRange(root, i, j, [&] (Node *&x) { clear(x); x = nullptr; });
  }
  template <class Comp> void erase(const Data &v, Comp cmp) {
    pair<int, Node *> p = getFirst(root, v, cmp);
    if (p.second && !cmp(p.second->val, v) && !cmp(v, p.second->val))
      erase_at(p.first);
  }
  void update(int i, const Lazy &v) {
    applyToRange(root, i, i, [&] (Node *&x) { x->apply(v); });
  }
  template <const int _ = Node::RANGE_UPDATES>
  typename enable_if<_>::type update(int i, int j, const Lazy &v) {
    if (i <= j) applyToRange(root, i, j, [&] (Node *&x) { x->apply(v); });
  }
  template <const int _ = Node::RANGE_REVERSALS>
  typename enable_if<_>::type reverse(int i, int j) {
    if (i <= j) applyToRange(root, i, j, [&] (Node *&x) { x->reverse(); });
  }
  int size() { return root ? root->sz : 0; }
  Data at(int i) { return select(root, i)->val; }
  template <class Comp>
  pair<int, Data *> lower_bound(const Data &v, Comp cmp) {
    pair<int, Node *> p = getFirst(root, v, cmp);
    return make_pair(p.first, p.second ? &p.second->val : nullptr);
  }
  template <class Comp>
  pair<int, Data *> upper_bound(const Data &v, Comp cmp) {
    return lower_bound(v, [&] (const Data &a, const Data &b) {
      return !cmp(b, a);
    });
  }
  template <class Comp> pair<int, Data *> find(const Data &v, Comp cmp) {
    pair<int, Data *> ret = lower_bound(v, cmp);
    if (!ret.second || cmp(v, *(ret.second)) || cmp(*(ret.second), v))
      return make_pair(size(), nullptr);
    return ret;
  }
  template <const int _ = Node::RANGE_QUERIES>
  typename enable_if<_, Data>::type query(int i, int j) {
    Data ret = Node::qdef();
    if (i <= j) applyToRange(root, i, j, [&] (Node *&x) { ret = x->sbtr; });
    return ret;
  }
  vector<Data> values() {
    vector<Data> ret; ret.reserve(size());
    function<void(Node *)> dfs = [&] (Node *x) {
      if (!x) return;
      x->propagate(); dfs(x->l); ret.push_back(x->val); dfs(x->r);
    };
    dfs(root); return ret;
  }
};


text:
#pragma once
#include <bits/stdc++.h>
using namespace std;

// Sample node structs for Splay, DynamicRangeOperations,
//   and LinkCutTree with different required fields required for each

// Sample node class for a single value of type T, supporting range reversals,
//   and point assignment
// Template Arguments:
//   T: the type of value to store
// Constructor Arguments:
//   v: the value of type Data to store
// Fields:
//   Data: the data type, equivalent to T
//   Lazy: the lazy type, equivalent to T
//   static const RANGE_UPDATES: a boolean indicating whether range updates
//     are permitted
//   static const RANGE_QUERIES: a boolean indicating whether range queries
//     are permitted
//   static const RANGE_REVERSALS: a boolean indicating whether range reversals
//     are permitted
//   rev: a boolean indicating whether the subtree needs to be reversed
//   sz: the number of nodes in the subtree
//   l: a pointer to the left child
//   r: a pointer to the right child
//   p: a pointer to the parent
//   val: the value of type Data being stored
// Functions:
//   update(): updates the current node's information based on its children
//   propagate(): propagates the current node's lazy information (including
//     rev) to its children
//   apply(v): applies the lazy value v to the node
//   reverse(): reverse this node's subtree (lazy flags
//     should be reversed)
// Tested:
//   https://dmoj.ca/problem/ds4
//   https://codeforces.com/contest/1288/problem/E
//   https://codeforces.com/contest/863/problem/D
//   https://codeforces.com/contest/13/problem/E
//   https://oj.uz/problem/view/JOI13_synchronization
template <class T> struct NodeVal {
  using Data = T; using Lazy = Data;
  static const bool RANGE_UPDATES = false, RANGE_QUERIES = false;
  static const bool RANGE_REVERSALS = true;
  bool rev; int sz; NodeVal *l, *r, *p; Data val;
  NodeVal(const Data &v)
      : rev(false), sz(1), l(nullptr), r(nullptr), p(nullptr), val(v) {}
  void update() {
    sz = 1;
    if (l) sz += l->sz;
    if (r) sz += r->sz;
  }
  void propagate() {
    if (rev) {
      if (l) l->reverse();
      if (r) r->reverse();
      rev = false;
    }
  }
  void apply(const Lazy &v) { val = v; }
  void reverse() { rev = !rev; swap(l, r); }
};

// Sample node class for aggregate range queries using a struct to combine
//   Data and Lazy, along with range reversals, and point assignment
// Template Arguments:
//   C: struct to combine data and lazy values
//     Required Fields:
//       Data: the data type
//       Lazy: the lazy type
//     Required Functions:
//       static qdef(): returns the query default value of type Data
//       static merge(l, r): returns the values l of type Data merged with
//         r of type Data, must be associative
//       static applyLazy(l, r): returns the value r of type Lazy applied to
//         l of type Data, must be associative
//       static revData(v): reverses the value v of type Data
//     Sample Struct: supporting point increments and range max queries
//       struct C {
//         using Data = int;
//         using Lazy = int;
//         static Data qdef() { return numeric_limits<int>::min(); }
//         static Data merge(const Data &l, const Data &r) {
//           return max(l, r);
//         }
//         static Data applyLazy(const Data &l, const Lazy &r) {
//           return l + r;
//         }
//         static void revData(Data &v) {}
//       };
// Constructor Arguments:
//   v: the value of type Data to store
// Fields:
//   Data: the data type, equivalent to C::Data
//   Lazy: the lazy type, equivalent to C::Lazy
//   static const RANGE_UPDATES: a boolean indicating whether range updates
//     are permitted
//   static const RANGE_QUERIES: a boolean indicating whether range queries
//     are permitted
//   static const RANGE_REVERSALS: a boolean indicating whether range reversals
//     are permitted
//   rev: a boolean flag indicating whether the subtree needs to be reversed
//   sz: the number of nodes in the subtree
//   l: a pointer to the left child
//   r: a pointer to the right child
//   p: a pointer to the parent
//   val: the value of type Data being stored
//   sbtr: the aggregate value of type Data for the subtree
// Functions:
//   update(): updates the current node's information based on its children
//   propagate(): propagates the current node's lazy information (including
//     rev) to its children
//   apply(v): applies the lazy value v to the node
//   reverse(): reverse this node's subtree (aggregate data and any
//     lazy flags should be reversed)
//   static qdef(): returns the query default value for the struct C
// Tested:
//   https://dmoj.ca/problem/dmpg17g2
//   https://dmoj.ca/problem/coi08p2
//   https://www.spoj.com/problems/QTREE2/
//   https://judge.yosupo.jp/problem/dynamic_tree_vertex_set_path_composite
template <class C> struct NodeAgg {
  using Data = typename C::Data; using Lazy = typename C::Lazy;
  static const bool RANGE_UPDATES = false, RANGE_QUERIES = true;
  static const bool RANGE_REVERSALS = true;
  bool rev; int sz; NodeAgg *l, *r, *p; Data val, sbtr;
  NodeAgg(const Data &v)
      : rev(false), sz(1), l(nullptr), r(nullptr), p(nullptr),
        val(v), sbtr(v) {}
  void update() {
    sz = 1; sbtr = val;
    if (l) { sz += l->sz; sbtr = C::merge(l->sbtr, sbtr); }
    if (r) { sz += r->sz; sbtr = C::merge(sbtr, r->sbtr); }
  }
  void propagate() {
    if (rev) {
      if (l) l->reverse();
      if (r) r->reverse();
      rev = false;
    }
  }
  void apply(const Lazy &v) {
    val = C::applyLazy(val, v); sbtr = C::applyLazy(sbtr, v);
  }
  void reverse() { rev = !rev; swap(l, r); C::revData(sbtr); }
  static Data qdef() { return C::qdef(); }
};

// Sample node class for aggregate range queries and lazy range updates
//  using a struct to combine Data and Lazy, along with range reversals
// Template Arguments:
//   C: struct to combine data and lazy values
//     Required Fields:
//       Data: the data type
//       Lazy: the lazy type
//     Required Functions:
//       static qdef(): returns the query default value of type Data
//       static merge(l, r): returns the values l of type Data merged with
//         r of type Data, must be associative
//       static applyLazy(l, r): returns the value r of type Lazy applied to
//         l of type Data, must be associative
//       static applyLazy(l, r, k): returns the value r of type Lazy applied to
//         l of type Data over a segment of length k, must be associative
//       static mergeLazy(l, r): returns the values l of type Lazy merged with
//         r of type Lazy, must be associative
//       static revData(v): reverses the value v of type Data
//     Sample Struct: supporting range assignments and range sum queries
//       struct C {
//         using Data = int;
//         using Lazy = int;
//         static Data qdef() { return 0; }
//         static Lazy ldef() { return numeric_limits<int>::min(); }
//         static Data merge(const Data &l, const Data &r) { return l + r; }
//         static Data applyLazy(const Data &l, const Lazy &r, int k) {
//           return r * k;
//         }
//         static Lazy mergeLazy(const Lazy &l, const Lazy &r) { return r; }
//         static void revData(Data &v) {}
//       };
// Constructor Arguments:
//   v: the value of type Data to store
// Fields:
//   Data: the data type, equivalent to C::Data
//   Lazy: the lazy type, equivalent to C::Lazy
//   static const RANGE_UPDATES: a boolean indicating whether range updates
//     are permitted
//   static const RANGE_QUERIES: a boolean indicating whether range queries
//     are permitted
//   static const RANGE_REVERSALS: a boolean indicating whether range reversals
//     are permitted
//   rev: a boolean flag indicating whether the subtree needs to be reversed
//   sz: the number of nodes in the subtree
//   l: a pointer to the left child
//   r: a pointer to the right child
//   p: a pointer to the parent
//   lz: the value of type Lazy to be propagated
//   val: the value of type Data being stored
//   sbtr: the aggregate value of type Data for the subtree
// Functions:
//   update(): updates the current node's information based on its children
//   propagate(): propagates the current node's lazy information (including
//     rev) to its children
//   apply(v): applies the lazy value v to the node
//   reverse(): reverse this node's subtree (aggregate data and any
//     lazy flags should be reversed)
//   static qdef(): returns the query default value for the struct C
// Tested:
//   https://dmoj.ca/problem/acc1p1
//   https://dmoj.ca/problem/noi05p2
//   https://dmoj.ca/problem/ds5easy
//   https://judge.yosupo.jp/problem/dynamic_sequence_range_affine_range_sum
template <class C> struct NodeLazyAgg {
  using Data = typename C::Data; using Lazy = typename C::Lazy;
  static const bool RANGE_UPDATES = true, RANGE_QUERIES = true;
  static const bool RANGE_REVERSALS = true;
  bool rev; int sz; NodeLazyAgg *l, *r, *p; Lazy lz; Data val, sbtr;
  NodeLazyAgg(const Data &v)
      : rev(false), sz(1), l(nullptr), r(nullptr), p(nullptr),
        lz(C::ldef()), val(v), sbtr(v) {}
  void update() {
    sz = 1; sbtr = val;
    if (l) { sz += l->sz; sbtr = C::merge(l->sbtr, sbtr); }
    if (r) { sz += r->sz; sbtr = C::merge(sbtr, r->sbtr); }
  }
  void propagate() {
    if (rev) {
      if (l) l->reverse();
      if (r) r->reverse();
      rev = false;
    }
    if (lz != C::ldef()) {
      if (l) l->apply(lz);
      if (r) r->apply(lz);
      lz = C::ldef();
    }
  }
  void apply(const Lazy &v) {
    lz = C::mergeLazy(lz, v); val = C::applyLazy(val, v, 1);
    sbtr = C::applyLazy(sbtr, v, sz);
  }
  void reverse() { rev = !rev; swap(l, r); C::revData(sbtr); }
  static Data qdef() { return C::qdef(); }
};


text:
#pragma once
#include <bits/stdc++.h>
using namespace std;

// Generic Splay Tree node operations supporting a generic node class (such
//   as the structs in BSTNode)
// Can be used in conjunction with DynamicRangeOperations to support
//   range operations using splay node operations
// Indices are 0-indexed and ranges are inclusive
// Template Arguments:
//   Node: a generic node class (sample structs are in BSTNode)
//     Required Fields:
//       sz: the number of nodes in the subtree
//       l: a pointer to the left child
//       r: a pointer to the right child
//       p: a pointer to the parent
//       val: only required if getFirst is called, the value being stored
//     Required Functions:
//       constructor(v): initializes a node with the value v
//       update(): updates the current node's information based on its children
//       propagate(): propagates the current node's lazy information (including
//         rev) to its children
//   Container: a container to contain Node objects (or some child class of
//     Node), recommended to use deque<Node> or vector<Node> if there is
//    a fixed number of nodes and TR can be reserved beforehand
// Fields:
//   TR: a container of type Container to store the nodes (including
//     potentially deleted nodes)
//   deleted: a deque of node pointers to store deleted nodes
// Functions:
//   splay(x): splays the node x to the root of the tree
//   makeNode(v): creates a new node passing v to the node constructor
//   applyToRange(root, i, j, f): applies the function f (accepting a
//     node pointer or reference to a node pointer) to a node x where x
//     is the disconnected subtree with indices in the range [i, j] for the
//     tree rooted at root (passed by reference)
//   select(root, k): returns the kth node (0-indexed) in the subtree of root,
//     and makes it the new root (or the last node accessed if null)
//   index(root, x): returns the index of node x in the tree rooted at root,
//     and makes it the new root
//   getFirst(root, v, cmp): returns the first node y (and its index) in the
//     tree rooted at root where cmp(y->val, v) returns false, and makes it the
//     new root (or the last node accessed if null)
//   build(A): builds a splay tree on the array A
//   clear(x): adds all nodes in the subtree of x to the deleted buffer
// In practice, has a moderate constant, not as fast as segment trees
// Time Complexity:
//   build, clear: O(N)
//   makeNode: O(1)
//   splay, applyToRange, select, index, getFirst: O(log N) amortized
// Memory Complexity: O(N)
// Tested:
//   https://dmoj.ca/problem/ds4 (applyToRange, select, getFirst)
//   https://codeforces.com/contest/1288/problem/E (applyToRange, index)
//   https://codeforces.com/contest/863/problem/D (applyToRange)
//   https://dmoj.ca/problem/dmpg17g2 (applyToRange)
//   https://dmoj.ca/problem/acc1p1 (applyToRange)
//   https://dmoj.ca/problem/noi05p2 (applyToRange)
//   https://judge.yosupo.jp/problem/dynamic_sequence_range_affine_range_sum
//     (applyToRange)
template <class Node, class Container = deque<Node>> struct Splay {
  Container TR; deque<Node *> deleted;
  template <class T> Node *makeNode(const T &v) {
    if (deleted.empty()) { TR.emplace_back(v); return &TR.back(); }
    Node *x = deleted.back(); deleted.pop_back();
    *x = typename Container::value_type(v); return x;
  }
  bool isRoot(Node *x) { return !x->p || (x != x->p->l && x != x->p->r); }
  void connect(Node *x, Node *p, bool hasCh, bool isL) {
    if (x) x->p = p;
    if (hasCh) (isL ? p->l : p->r) = x;
  }
  void rotate(Node *x) {
    Node *p = x->p, *g = p->p; bool isRootP = isRoot(p), isL = x == p->l;
    connect(isL ? x->r : x->l, p, true, isL); connect(p, x, true, !isL);
    connect(x, g, !isRootP, !isRootP && p == g->l); p->update();
  }
  void splay(Node *x) {
    while (!isRoot(x)) {
      Node *p = x->p, *g = p->p; if (!isRoot(p)) g->propagate();
      p->propagate(); x->propagate();
      if (!isRoot(p)) rotate((x == p->l) == (p == g->l) ? p : x);
      rotate(x);
    }
    x->propagate(); x->update();
  }
  template <class F> void applyToRange(Node *&root, int i, int j, F f) {
    if (i == 0 && j == (root ? root->sz : 0) - 1) {
      f(root); if (root) { root->propagate(); root->update(); }
    } else {
      Node *t = i ? select(root, i - 1)->r : select(root, j + 1)->l;
      connect(nullptr, root, true, !i); root->update();
      connect(t, nullptr, false, !i); applyToRange(t, 0, j - i, f);
      connect(t, root, true, !i); root->update();
    }
  }
  Node *select(Node *&root, int k) {
    Node *last = nullptr; while (root) {
      (last = root)->propagate(); int t = root->l ? root->l->sz : 0;
      if (t > k) root = root->l;
      else if (t < k) { root = root->r; k -= t + 1; }
      else break;
    }
    if (last) splay(root = last);
    return root;
  }
  int index(Node *&root, Node *x) {
    root = x; if (!root) return -1;
    splay(root); return root->l ? root->l->sz : 0;
  }
  template <class T, class Comp>
  pair<int, Node *> getFirst(Node *&root, const T &v, Comp cmp) {
    pair<int, Node *> ret(0, nullptr); Node *last = nullptr; while (root) {
      (last = root)->propagate();
      if (!cmp(root->val, v)) { ret.second = root; root = root->l; }
      else { ret.first += 1 + (root->l ? root->l->sz : 0); root = root->r; }
    }
    if (last) splay(root = last);
    return ret;
  }
  template <class T> Node *buildRec(const vector<T> &A, int l, int r) {
    if (l > r) return nullptr;
    int m = l + (r - l) / 2; Node *left = buildRec(A, l, m - 1);
    Node *ret = makeNode(A[m]), *right = buildRec(A, m + 1, r);
    connect(left, ret, ret, true); connect(right, ret, ret, false);
    ret->update(); return ret;
  }
  template <class T>
  Node *build(const vector<T> &A) { return buildRec(A, 0, int(A.size()) - 1); }
  void clear(Node *x) {
    if (!x) return;
    clear(x->l); deleted.push_back(x); clear(x->r);
  }
};


text:
#pragma once
#include <bits/stdc++.h>
using namespace std;

// Bottom up 2D segment tree supporting point updates and range queries
// Indices are 0-indexed and ranges are inclusive
// Template Arguments:
//   C: struct to combine data and lazy values
//     Required Fields:
//       Data: the data type
//       Lazy: the lazy type
//     Required Functions:
//       static qdef(): returns the query default value of type Data
//       static merge(l, r): returns the values l of type Data merged with
//         r of type Data, must be associative
//       static applyLazy(l, r): returns the value r of type Lazy applied to
//         l of type Data, must be associative
//     Sample Struct: supporting point increments and range max queries
//       struct C {
//         using Data = int;
//         using Lazy = int;
//         static Data qdef() { return numeric_limits<int>::min(); }
//         static Data merge(const Data &l, const Data &r) {
//           return max(l, r);
//         }
//         static Data applyLazy(const Data &l, const Lazy &r) {
//           return l + r;
//         }
//       };
// Constructor Arguments:
//   N: the size of the first dimension of the array
//   M: the size of the second dimension of the array
//   A: a 2D vector of elements of type Data
//   vdef: the default value to fill the array with
// Functions:
//   update(i, j, v): updates the value A[i][j] with the lazy value v
//   query(u, d, l, r): queries the range [u, d] in the first dimension and
//     [l, r] in the second dimension and returns the aggregate value
// In practice, has a small constant, not quite as fast as fenwick trees
// Time Complexity:
//   constructor: O(NM)
//   update, query: O(log N log M)
// Memory Complexity: O(NM)
// Tested:
//   Fuzz and Stress Tested
template <class C> struct SegmentTreeBottomUp2D {
  using Data = typename C::Data; using Lazy = typename C::Lazy;
  int N, M; vector<vector<Data>> TR;
  void build() {
    for (int i = 0; i < N; i++) for (int j = M - 1; j > 0; j--)
      TR[N + i][j] = C::merge(TR[N + i][j * 2], TR[N + i][j * 2 + 1]);
    for (int i = N - 1; i > 0; i--) {
      for (int j = 0; j < M; j++)
        TR[i][M + j] = C::merge(TR[i * 2][M + j], TR[i * 2 + 1][M + j]);
      for (int j = M - 1; j > 0; j--)
        TR[i][j] = C::merge(TR[i][j * 2], TR[i][j * 2 + 1]);
    }
  }
  SegmentTreeBottomUp2D(const vector<vector<Data>> &A)
      : N(A.size()), M(N == 0 ? 0 : A[0].size()),
        TR(N * 2, vector<Data>(M * 2, C::qdef())) {
    for (int i = 0; i < N; i++)
      copy(A[i].begin(), A[i].end(), TR[N + i].begin() + M);
    build();
  }
  SegmentTreeBottomUp2D(int N, int M, const Data &vdef)
      : N(N), M(M), TR(N * 2, vector<Data>(M * 2, C::qdef())) {
    for (int i = 0; i < N; i++)
      fill(TR[N + i].begin() + M, TR[N + i].end(), vdef);
    build();
  }
  void update(int i, int j, const Lazy &v) {
    for (int ii = N + i; ii > 0; ii /= 2) {
      if (ii == N + i) TR[N + i][M + j] = C::applyLazy(TR[N + i][M + j], v);
      else TR[ii][M + j] = C::merge(TR[ii * 2][M + j], TR[ii * 2 + 1][M + j]);
      for (int jj = M + j; jj /= 2;)
        TR[ii][jj] = C::merge(TR[ii][jj * 2], TR[ii][jj * 2 + 1]);
    }
  }
  Data query(int u, int d, int l, int r) {
    auto query = [&] (int i, int l, int r) {
      Data ql = C::qdef(), qr = C::qdef();
      for (l += M, r += M; l <= r; l /= 2, r /= 2) {
        if (l % 2) ql = C::merge(ql, TR[i][l++]);
        if (!(r % 2)) qr = C::merge(TR[i][r--], qr);
      }
      return C::merge(ql, qr);
    };
    Data qu = C::qdef(), qd = C::qdef();
    for (u += N, d += N; u <= d; u /= 2, d /= 2) {
      if (u % 2) qu = C::merge(qu, query(u++, l, r));
      if (!(d % 2)) qd = C::merge(query(d--, l, r), qd);
    }
    return C::merge(qu, qd);
  }
};


text:
#pragma once
#include <bits/stdc++.h>
using namespace std;

// Top down segment tree supporting point updates and range queries,
//   with a lazy template argument to enable range updates
// Indices are 0-indexed and ranges are inclusive
// Template Arguments:
//   LAZY: boolean to indicate whether or not range updates are enabled
//   C: struct to combine data and lazy values
//     Required Fields:
//       Data: the data type
//       Lazy: the lazy type
//     Required Functions:
//       static qdef(): returns the query default value of type Data
//       static ldef(): only required if LAZY is true, returns the lazy
//         default value of type Lazy
//       static merge(l, r): returns the values l of type Data merged with
//         r of type Data, must be associative
//       static applyLazy(l, r): only required if LAZY is false, returns the
//         value r of type Lazy applied to l of type Data, must be associative
//       static applyLazy(l, r, k): only required if LAZY is true, returns the
//         value r of type Lazy applied to l of type Data over a segment of
//         length k, must be associative
//       static mergeLazy(l, r): only required if LAZY is true, returns
//         the values l of type Lazy merged with r of type Lazy,
//         must be associative
//     Sample Struct: C1 supports point increments and range max queries,
//         while C2 supports range assignments and range sum queries
//       struct C1 {
//         using Data = int;
//         using Lazy = int;
//         static Data qdef() { return numeric_limits<int>::min(); }
//         static Data merge(const Data &l, const Data &r) {
//           return max(l, r);
//         }
//         static Data applyLazy(const Data &l, const Lazy &r) {
//           return l + r;
//         }
//       };
//       struct C2 {
//         using Data = int;
//         using Lazy = int;
//         static Data qdef() { return 0; }
//         static Lazy ldef() { return numeric_limits<int>::min(); }
//         static Data merge(const Data &l, const Data &r) { return l + r; }
//         static Data applyLazy(const Data &l, const Lazy &r, int k) {
//           return r * k;
//         }
//         static Lazy mergeLazy(const Lazy &l, const Lazy &r) { return r; }
//       };
// Constructor Arguments:
//   N: the size of the array
//   A: a vector of type C::Data
// Functions:
//   update(i, v): updates the index i with the lazy value v
//   update(l, r, v): update the range [l, r] with the lazy value v
//   query(l, r): queries the range [l, r] and returns the aggregate value
//   bsearchPrefix(l, r, f): returns the smallest index i in the range [l, r]
//     such that f(query(l, i)) returns true or r + 1 if none exist
//   bsearchSuffix(l, r, f): returns the largest index i in the range [l, r]
//     such that f(query(i, r)) returns true or l - 1 if none exist
// In practice, has a small constant, not quite as fast as fenwick trees
//   or bottom up non lazy segment trees,
//   and similar performance as bottom up lazy segment trees
// Time Complexity:
//   constructor: O(N)
//   update, query, bsearchPrefix, bsearchSuffix: O(log N)
// Memory Complexity: O(N)
// Tested:
//   https://dmoj.ca/problem/ds3 (LAZY = false)
//   https://dmoj.ca/problem/dmpg17g2 (LAZY = false)
//   https://dmoj.ca/problem/coci17c1p5 (LAZY = false, bsearchPrefix)
//   https://judge.yosupo.jp/problem/point_set_range_composite (LAZY = false)
//   https://dmoj.ca/problem/lazy (LAZY = true)
//   https://mcpt.ca/problem/seq3 (LAZY = true)
//   https://judge.yosupo.jp/problem/range_affine_range_sum (LAZY = true)
//   https://dmoj.ca/problem/dmopc17c4p6 (LAZY = true)
template <const bool LAZY, class C> struct SegmentTreeTopDown {
#define lazy_def template <const bool _ = LAZY> typename enable_if<_>::type
#define agg_def template <const bool _ = LAZY> typename enable_if<!_>::type
  using Data = typename C::Data; using Lazy = typename C::Lazy;
  int N; vector<Data> TR; vector<Lazy> LZ;
  lazy_def apply(int x, int tl, int tr, const Lazy &v) {
    TR[x] = C::applyLazy(TR[x], v, tr - tl + 1);
    if (x < int(LZ.size())) LZ[x] = C::mergeLazy(LZ[x], v);
  }
  agg_def apply(int x, int, int, const Lazy &v) {
    TR[x] = C::applyLazy(TR[x], v);
  }
  lazy_def propagate(int x, int tl, int tr) {
    if (LZ[x] != C::ldef()) {
      int m = tl + (tr - tl) / 2; apply(x * 2, tl, m, LZ[x]);
      apply(x * 2 + 1, m + 1, tr, LZ[x]); LZ[x] = C::ldef();
    }
  }
  agg_def propagate(int, int, int) {}
  void build(const vector<Data> &A, int x, int tl, int tr) {
    if (tl == tr) { TR[x] = A[tl]; return; }
    int m = tl + (tr - tl) / 2;
    build(A, x * 2, tl, m); build(A, x * 2 + 1, m + 1, tr);
    TR[x] = C::merge(TR[x * 2], TR[x * 2 + 1]);
  }
  void update(int x, int tl, int tr, int l, int r, const Lazy &v) {
    if (l <= tl && tr <= r) { apply(x, tl, tr, v); return; }
    propagate(x, tl, tr); int m = tl + (tr - tl) / 2;
    if (tl <= r && l <= m) update(x * 2, tl, m, l, r, v);
    if (m + 1 <= r && l <= tr) update(x * 2 + 1, m + 1, tr, l, r, v);
    TR[x] = C::merge(TR[x * 2], TR[x * 2 + 1]);
  }
  Data query(int x, int tl, int tr, int l, int r) {
    if (r < tl || tr < l) return C::qdef();
    if (l <= tl && tr <= r) return TR[x];
    propagate(x, tl, tr); int m = tl + (tr - tl) / 2;
    return C::merge(query(x * 2, tl, m, l, r),
                    query(x * 2 + 1, m + 1, tr, l, r));
  }
  template <class F>
  int bsearchPrefix(int x, int tl, int tr, int l, int r, Data &agg, F f) {
    if (r < tl || tr < l) return r + 1;
    if (tl != tr) propagate(x, tl, tr);
    if (l <= tl && tr <= r) {
      Data v = C::merge(agg, TR[x]); if (!f(v)) { agg = v; return r + 1; }
    }
    if (tl == tr) return tl;
    int m = tl + (tr - tl) / 2;
    int ret = bsearchPrefix(x * 2, tl, m, l, r, agg, f);
    return ret <= r ? ret : bsearchPrefix(x * 2 + 1, m + 1, tr, l, r, agg, f);
  }
  template <class F>
  int bsearchSuffix(int x, int tl, int tr, int l, int r, Data &agg, F f) {
    if (r < tl || tr < l) return l - 1;
    if (tl != tr) propagate(x, tl, tr);
    if (l <= tl && tr <= r) {
      Data v = C::merge(TR[x], agg); if (!f(v)) { agg = v; return l - 1; }
    }
    if (tl == tr) return tl;
    int m = tl + (tr - tl) / 2;
    int ret = bsearchSuffix(x * 2 + 1, m + 1, tr, l, r, agg, f);
    return l <= ret ? ret : bsearchSuffix(x * 2, tl, m, l, r, agg, f);
  }
  SegmentTreeTopDown(int N)
      : N(N), TR(N == 0 ? 0 : 1 << __lg(N * 4 - 1), C::qdef()) {
    if (LAZY) LZ.resize(N == 0 ? 0 : 1 << __lg(N * 2 - 1), C::ldef());
  }
  SegmentTreeTopDown(const vector<Data> &A) : SegmentTreeTopDown(A.size()) {
    if (N > 0) { build(A, 1, 0, N - 1); }
  }
  lazy_def update(int l, int r, const Lazy &v) {
    update(1, 0, N - 1, l, r, v);
  }
  void update(int i, const Lazy &v) { update(1, 0, N - 1, i, i, v); }
  Data query(int l, int r) { return query(1, 0, N - 1, l, r); }
  template <class F> int bsearchPrefix(int l, int r, F f) {
    Data agg = C::qdef(); return bsearchPrefix(1, 0, N - 1, l, r, agg, f);
  }
  template <class F> int bsearchSuffix(int l, int r, F f) {
    Data agg = C::qdef(); return bsearchSuffix(1, 0, N - 1, l, r, agg, f);
  }
#undef lazy_def
#undef agg_def
};